The simplest setting where RL could be understood is 'bandits'. Bandits correspond to the setup where the agent has a set of actions to choose from, after choosing an action, the agent recieves a reward. Over the course of interacting multiple times, for each step it has to choose the action that maximizes the reward. As the simplest case, here, the episode ends with a single action, we didn't talk about state yet, because there is no notion of state in this setting. The name and setting is inspired from the slot machines used in gambling, where an investor has to pull a lever amongst many on a machine by paying some fee, ideally the investor chooses to pull a lever such that it will maximize the return on its investment. Because of a large single lever they are also called one-armed bandit. For RL this arm will correspond to an action that agent can take.
From our RL formulation, for a bandit with \(K\) arms, if an agent chooses to pull arm \(k\), call this action \(a_k\), it will get some reward \(r(a_k)\),
in the quest of maximizing cumulative reward (which is simply reward here) the action with maximum expected reward will be chosen, hence,
\(a_k = \arg\max_{k} (r(a_k))\). When we expand this term to consider experiences across episodes, it will be written as, \(\arg\max_k (Q(a_k))\),
where \(Q_a\) is the expected reward after taking an action a, hence also called 'action value'. We will estimate \(Q(a_k)\) from our past interactions as,
\[Q(a) = \frac{\sum_t r_t(a)}{N(a)}\]
here, \(N(a)\) is number of times an action a was chosen, \(R_t(a)\) is reward obtained by choosing action a in episode t.
A precise formulation could be given as,
\[Q_n(a_k) = \frac{\sum_{t\in{0\to(n-1)}} r_t(a_k)}{n-1}\]
The estimated return of an candidate action \(a_k\) at episode \(n\), \(Q_n(a_k)\), is the average of total reward obtained by choosing
that action across previous episodes. We can also write the estimate for next episode as,
\[Q_{n+1}(a_k) = \frac{r_n(a_k)+r_1(a_k)+r_2(a_k)+ ... + r_{n-1}(a_k)}{n}\]
\[ = \frac{r_n(a_k)}{n}+\frac{(n-1)Q_n(a_k)}{n}\]
\[ = Q_n(a_k) + \frac{(r_n(a_k) - Q_n(a_k))}{n}\]
\[ = Q_n(a_k) + \frac{1}{n} (r_n(a_k) - Q_n(a_k))\]
\[Q_{n+1}(a_k) = Q_n(a_k) + \alpha (r_n(a_k) - Q_n(a_k))\]
here, \(\alpha = \frac{1}{n}\), is called as a step size, \((r_n - Q_n)\) can be thought of the error in estimation of the reward.
This style of recursive estimation make our calculations efficient.
As discussed above, the action (arm to be pulled) is selected as \(\arg\max_k (Q_n(a_k))\). This is called as a greedy policy.
Instead of always choosing a greedy (highest estimated \(Q\)) action, we can allow for agent to explore other actions as well.
One instance of such policy is \(\epsilon\)-greedy policy, where with \(\epsilon\) probability, an agent can choose to explore
and choose a random action, and with (\(1-\epsilon\)) probability, it can choose the action with highest estimated return.
Choosing a highest estimated return action is called 'explotation', since the agent is exploiting the available information
in hope of getting the best return. And choosing other action is simply 'exploration', since an agent is trying to take new action
in hope of gathering more information and maybe even better returns than what is known. The values of \(\epsilon\) decides
how much we allow agent to trade-off between exploration and exploitation.
We can write the greedy policy as \(\pi = \arg\max_k (Q(a_k))\), and the \(\epsilon\)-greedy policy as,
\[\pi = \begin{cases}
Random(1 \to K) \text{, with probability } \epsilon\\
\arg\max_k (Q(a_k)) \text{, with probability } 1-\epsilon
\end{cases}
\]
Exploring randomly isn't necessarily the best way to gather information for an agent. Instead the agent could start with
the assumption that every action is a good action, this strategy allows a wider exploration early on covering all actions and
inform that in its later decision making. This can be achieved by assigning high initial expected action estimation,
i.e. \(Q_0(a_k) = z\), where \(z\) is a high positive number. This strategy is called optimistic exploration.
In the estimation of expected return, we allow agent to learn from its past experiences.
Similar can be allowed for the policy, based on agent's past experiences it can include some confidence associated with its estimation.
One such method is 'Upper Confidence Bound', this associates the confidence with number of times it experienced that action. Which could be written as,
\[\pi = \arg\max_k \left[ Q(a_k) + c \sqrt{\frac{\ln{t}}{N(a_k)}} \right] \]
here, the term \(\frac{1}{N(a_k)}\) expands on the idea of optimism in face of uncertainty, which is associated with limited experience with that action.
Hence, the tendency to explore and choose suboptimal action will reduce with experience, which will be informed by their consistent low returns.
In this article we discussed the simplest setting in RL, defined returns estimation and choosing action based on our estimations.
9 Feb 2025.
Next in series: Gradient Bandit.