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

Question

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.

Answer 1

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.

Answer 2

Let's start the table of Zhang Kin from one, not zero. Because in this question, it's given $Q_1(a)=0$ for all $a=1,2,3,4$.

By using the table starting at one since the action of $A_2=2$, this action can be an exploration or exploitation (Choosing randomly between maximum values of $Q(1)$ which are zero or randomly choosing between all slots 1,2,3,4). The third action $A_3=2$ should be greedy since we have $Q(2)=-1,1,0,0$ and 1 is the maximum (although it can be an exploration).

The fourth action, $A_4=2$, is an exploration because the values of $Q$ are $Q(3)=-1,-1/2,0,0$, and if we had followed the greedy method, we would have chosen action 3 or 4.

And at last, for the 5th action, which is $A_5=3$ again, it is an exploration. Because $Q(4)=-1,1/3,0,0$ and if we had taken maximum, we would choose the action of $A_5=2$.

Answer 3

Replying to Zhang Kin Question:

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?

Answer: It’s given that Q1(a)=0 for all 𝑎=1,2,3,4

*Note when A1=1 means A1 means ‘Action at 1st iteration’ and =1 means “Action = 1st”, and so on is for A2=2, it means at 2nd iteration the action was 2.

The first action A1=1, this action can be either exploration or exploitation (Choosing randomly between maximum values of 𝑄(1) which are zero or randomly choosing between all slots 1,2,3,4).

The second action A2=2 is the exploration, as we have the value of 𝑄(1) = -1,0,0,0.

The third action A3=2 should be greedy since we have Q(2)= −1,1,0,0 and 1 is the maximum (although it can be an exploration).

The fourth action, A4=2, is an exploration because the values of Q are Q(3)= −1,−0.5,0,0, and if we had followed the greedy method, we would have chosen action 3 or 4.

And at last, for the fifth action, which is A5=3 again, it is an exploration. Because Q(4)= −1,1/3,0,0 and if we had taken maximum, we would choose the action of A5=2.

Answer 4

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?

Answer 5

An $\epsilon-$greedy policy means that when deciding which action to take next we:

with probability $1-\epsilon$, pick the action with the highest estimated value (exploitation)

with probability $\epsilon$, pick an action at random (exploration)

In the exercise we are told the following actions and rewards "A1 = 1, R1 = 1, A2 = 2, R2 = 1, A3 = 2, R3 = 2, A4 = 2, R4 = 2, A5 = 3, R5 = 0." However we are not told whether these actions were picked from exploitation or exploration.

The exercise asks :

""

On some of these time steps the $\epsilon$ case may have occurred, causing an action to be selected at random.

1. On which time steps could this possibly have occurred?
2. On which time steps did this definitely occur?

""

The answer is :

1. At every time step this $\textit{could}$ have occurred, since at every time step with probability $\epsilon$ we take an exploration action.
2. To find the time steps where exploration definitely occurred we just need to identify the $t$ such that $$A_t \neq \text{argmax}_a Q_t(a). $$ This happens at $t=2,5$. Note as Sutton explains $Q_t(a)$ is calculated via the sample average $$Q_a(t) = \frac{\text{sum of rewards when $a$ taken prior to $t$}}{\text{number of times $a$ taken prior to $t$}}.$$ $$$$