2
$\begingroup$

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.

$\endgroup$

4 Answers 4

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – ARAT
    Sep 6, 2018 at 19:26
  • $\begingroup$ Good point, I'm not sure how I missed that! $\endgroup$
    – combo
    Sep 7, 2018 at 20:57
  • $\begingroup$ 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 ? $\endgroup$
    – Satml
    Apr 25, 2021 at 20:09
1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ I'm using the table of the Zhang Kin answer. $\endgroup$
    – Ali
    Jul 14, 2022 at 17:25
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.