# How to understand k-armed bandit example from Sutton's RL book chapter 2?

I have a trivial problem but I do not understand fully the k-armed bandit theorem from chapter 2. My question is based on Sutton's "Reinforcement Learning: An introduction, second edition". The exercise is as such:

Consider a k-armed bandit problem with k = 4 actions, denoted 1, 2, 3, and 4. Consider applying to this problem a bandit algorithm using ε-greedy action selection, sample-average action-value estimates, and initial estimates of Q1(a) = 0, for all a. Suppose the initial sequence of actions and rewards is A1 = 1, R1 = 1, A2 = 2, R2 = 1, A3 = 2, R3 = 2, A4 = 2, R4 = 2, A5 = 3, R5 = 0. On some of these time steps the ε case may have occurred, causing an action to be selected at random. On which time steps did this definitely occur? On which time steps could this possibly have occurred?

My assumption was as such: A1 may have been chosen both randomly or deliberately (no info about that provided), A2 may have been random (as exploration), A3 and A4 were greedy and A5 was explored. So my answer to the question:

On which time steps did this definitely occur?

would be that actions A5 was definitelly random (not sure about A1 and A2).

How to answer this correctly and the second question as well? What I do not quite get here is why the immediate rewards (R3 and R4) are equal to 2 when they should be chosen among 0 (lose) and 1 (win). I would understand that the action-values Q3(a) and Q4(a) may be equal to 2 but this R3, R4 confused me. Could someone provide me the proper way of solving this problem step by step? This would help me to understand the essence of the k-armed bandit theorem.

From what you posted, I don't see where the rewards are constrained to 0,1. Generally rewards can be real-valued.

To understand the algorithm, let's write down the estimates after each iteration. I'll use the format Iteration: estimate of Q(1),Q(2),Q(3),Q(4)

0: 0, 0, 0, 0

1: 1, 0, 0, 0

2: 1, 1, 0, 0

3: 1, 1.5, 0, 0

4: 1, 1.67, 0, 0

5: 1, 1.67, 0, 0

Now consider how the algorithm works.

At iteration 1, it could either pick action 1 by default or pick it randomly - we really can't say.

At iteration 2, it should pick action 1 since that has the largest estimate. Since it picks action 2, we know this is an exploration action.

At iteration 3, it should pick 2 so this is greedy.

You should be able to use this reasoning to deduce that A4 is an exploitation action and A5 was an exploration action.

• There is something i did not comprehend fully. Why at iteration 3, you say it should pick either action 1 or action 2? it is obvious action 2 at iteration 3 gives the highest estimate value of the action and the agent goes for action 2. is not it exploitation already? is it because at iteration 2, even though the agent goes for action 2, but the estimated values of action 1 and action 2 at iteration 2 are the same so basically, it cannot be named as exploiting so we are not sure about tie-breaking
– ARAT
Sep 6, 2018 at 19:26
• Good point, I'm not sure how I missed that! Sep 7, 2018 at 20:57
• I dont understand when Combo said, for time 3, it supposed to chose 2. Since there is tie for Q values between Action = 1 and Action = 2, it can be chosen any of action 1 or 2 right ? Apr 25, 2021 at 20:09

Firstly, the exercise has a negative reward I think the copy action miss the minus symbol The whole exercise is：

Exercise 2.2: Bandit example Consider a k-armed bandit problem with k = 4 actions, denoted 1, 2, 3, and 4. Consider applying to this problem a bandit algorithm using ε-greedy action selection, sample-average action-value estimates, and initial estimates of $$Q_1(a) = 0$$, for all a. Suppose the initial sequence of actions and rewards is $$A_1 = 1, R_1 = -1, A_2 = 2, R_2 = 1, A_3 = 2, R_3 = -2, A_4 = 2, R_4 = 2, A_5 = 3, R_5 = 0$$. On some of these time steps the $$\varepsilon$$ case may have occurred, causing an action to be selected at random. On which time steps did this definitely occur? On which time steps could this possibly have occurred?

Here is the table:

Time Action ($$A_i$$) Reward ($$R_i$$)
1 1 -1
2 2 1
3 2 -2
4 2 2
5 3 0

My explanation: First, convert Reward to Q: $${Q_t}(a) = \frac{{\sum\limits_{i = 1}^{t - 1} {{R_i}{1_{{A_i} = a}}} }}{{\sum\limits_{i = 1}^{t - 1} {{1_{{A_i} = a}}} }}$$

Iteration = Time Q(1) Q(2) Q(3) Q(4)
0 0 0 0 0
1 -1 0 0 0
2 -1 1 0 0
3 -1 -0.5 0 0
4 -1 1/3 0 0
5 -1 1/3 0 0

So at time1 & time3 there are more than one max action (possible occur) time2,4,5 we have the max Q value which response to action 2

But I still have problems with time 4 since I found other blog which said time 4 does not definitely occur, and also about the $$\varepsilon$$ case it's about the probability what's the meaning about the question must occur?