Why is the expected reward of this $\epsilon = 0$ greedy algorithm equal to 1?

Question

I am learning Reinforcement Learning and the concept of $\epsilon$-greedy algorithms. In an example on page 28 of Richard Sutton's book Reinforcement Learning: An Introduction, second edition, there was an example of a multi-armed bandit problem ran for empirical solutions called the ten-armed testbed.

The example is defined as follows: This was a set of 2000 randomly generated k-armed bandit problems with $k = 10$. For each bandit problem, the action values, $q_{*}(a), a = 1, . . . , 10$, were selected according to a normal (Gaussian) distribution with mean 0 and variance 1. Then, when a learning method applied to that problem selected action $A_{t}$ at time step $t$, the actual reward, $R_{t}$, was selected from a normal distribution with mean $q_{*}(A_{t})$ and variance 1

Varying levels of $\epsilon$ were tried, and it produced the average reward over time for each $\epsilon$. The figure is seen below.

My confusion comes from when $\epsilon$ is equal to 0. In this case, we take action which is the highest value of our estimates $Q_{t}(a)$ for each $t$. As we are effecively sampling from a "gaussian of a gaussian", then wouldn't the average reward over time always be 0? Why is that as the time steps increase, $\epsilon = 0$ always yields average reward equal to 1? Why is it, firstly, non-zero, and why is it 1?

Answer 1

Why is that as the time steps increase, 𝜖=0 always yields average reward equal to 1?

It does not always yield 1, but when averaged over many instances of the problem (2000 used in the plots), the mean reward is close to 1. The expected reward per time step in each instance of the environment can vary widely, and is limited by $\text{max}_a q_*(a)$.

For instance it is possible (with probability of 1 in 1024) that all 10 actions are assigned a mean less than zero. In which case, the best an agent can do is find the least negative action.

Why is it, firstly, non-zero, and why is it 1?

You would expect a random agent to have a zero mean result on the example environment. Greedy agents are not as effective as other strategies, as shown by the graph, but they are often significantly better than random agents.

The mean reward is non-zero because a greedy agent will still refine its estimates and because the estimates may change which the preferred action is, it is able to correct a proportion of early mistakes.

Here are two ways in which a greedy agent will prefer actions with a positive mean value:

• When pulled for the first time (and thus setting the initial estimate for that bandit), an action with a negative mean value is more likely to return a negative reward. Once the agent has experienced a negative value from the first pull, it will avoid that action until all other estimates are below it.

• If by chance the first chosen action with a negative mean reward returns the best reward so far (due to variance in individual rewards), it will get chosen again on next actions. Over successive time steps, the estimated mean will become closer to the true mean for that action. As that true mean is negative, it will drop below initial estimates of zero. Provided at least one other action has not been chosen yet, that other action will become preferred by the agent.

There can be many more complex interplays between initial estimates when using a greedy agent. In general, any initial estimate that is by chance too high and cause the agent to select that action will self-correct becasue it will get sampled again. That in turn may reduce the estimate to where it is below some other action's estimate, making a different action the preferred greedy choice. This sequence of events will preferentially select better actions on average.

The greedy agent does not easily correct estimates that start too low such that the actions never get selected again - it is common to see underestimates of the best few actions where those estimates are lower than the true value of the $n^{th}$ best action, so it is that $n^{th}$ best action that gets chosen in the long term. However, there is still a bias towards low values of $n$, with $n=1$ (i.e. choosing the best action) being most likely.

The same chapter of Sutton & Barto covers optimistic initialisation, which can take advantage of this behaviour of greedy action selection to drive a form of exploration.

The specific value close to $1.0$ seen in the experiment is mostly coincidence. It depends a lot on $k$, the number of possible actions, as well as the mean and standard deviation of course. I am not aware of any simple derivation from theory, and would be very surprised if the value was exactly $1.0$

Answer 2

Exploration allows an agent to improve its current knowledge about each action, hopefully leading to long-term benefit.

Exploitation chooses the greedy action to get the most reward, but by being greedy with respect to action-value estimates may lead to sub-optimal performance.

Agent can:

• explore (1)
• exploit (2)

When (1) it gets more accurate estimates of action-values. When (2) it might get more reward.

EE dilemma or Exploration-Exploitation dilemma is agent not able to choose (1) and (2)

So EG (epsilon-greedy) is a simple method to balance exploration and exploitation by choosing (1) and (2) at random.

EG $\epsilon =0$ case where epsilon refers to the probability of choosing to explore, exploits most of the time with a small chance of exploring. Because there is no exploring no success is made.