2
$\begingroup$

In the multi-armed bandit problem, I would like to clarify exactly what happens from time step $t=1$ in the context of the epsilon greedy strategy for $\epsilon=0$ and $0<\epsilon \leq 1$. By what I understood. For example, I am not sure exactly what the gambler does to determine the best strategy. Does he just go through the $k$ levers and sees what's the best one, so at time step $k+1$ he "starts" the greedy behaviour where he picks the best strategy until the $k+1$'th step with probability $1-\epsilon$ and then chooses randomly from all possible levers at each timstep with probability $\epsilon$?

$\endgroup$

1 Answer 1

2
$\begingroup$

You mention two options, $\epsilon=0$ and $\epsilon>0$.

For $\epsilon=0$ there is no exploration, it's all exploitation, so your agent will always select the arm with the maximal reward. If you star from the beginning and all the rewards are random or 0 then this is a very poor choice (you may still get some exploration if you break ties at random).

For $\epsilon>0$ at each time step you will with probability $1-\epsilon$ select the current best action (best lever), and with probability $\epsilon$ you will select an action (lever) at random. This does not change over time. This is done for exploration. In the end if you wanted to figure out what are the best actions you would look at the best actions only.

For $\epsilon=1$ all actions in all time steps are random, no exploitation.

$\endgroup$
9
  • $\begingroup$ for $\epsilon=0$, do we just continue with the bandit chosen at time step $t=1$? Or does there happen some kind of exploration to see what bandit yields the most reward? For example if we have 3 levers and only lever $1$ yields reward $1$ and the other ($2,3$) yield reward $0$, so we randomly pick lever $2$ and time step $t=1$, will this mean we will always pick lever $2$ when $\epsilon=0$? $\endgroup$
    – Slim Shady
    Commented Jan 12, 2022 at 9:44
  • $\begingroup$ @SlimShady This depends on what kind of reward you assigned to each bandit at the beginning. If all bandits have a reward of 0, then the gambler will choose the best bandit, which happens to be all 3 of them, so you will typically select one bandit at random. You will update this one bandits value and if the reward is negative then you will continue this procedure until there is exactly one max reward, then you will always select that best action (at that point). $\endgroup$ Commented Jan 12, 2022 at 9:52
  • $\begingroup$ So in my example at time step $t=1$ the gambler knows that lever $1$ yields the best reward, so he will choose lever $1$? So to my understanding the initial choice of lever is not random? I understand what $\epsilon$ means and that the probability of choosing the best lever is $1-\epsilon$. My original question is actually different. What happens at time step $t=1$ and how exactly does the gambler determine the lever which yields the best reward when $\epsilon =0$? For $\epsilon\neq 0$ it's more intuitive for me to understand since if the initial choice of lever is random then eventually $\endgroup$
    – Slim Shady
    Commented Jan 12, 2022 at 9:56
  • $\begingroup$ the gambler will get to the lever with best reward by exploring $\endgroup$
    – Slim Shady
    Commented Jan 12, 2022 at 10:00
  • $\begingroup$ @SlimShady As I said, you have to decide the reward of each lever (bandit) at the start, you have to provide this information. Usually you either give each lever a reward of 0 (or some other constant), meaning all levers are equally rewarding at the start, or you give each lever some small random reward. This is just some guess. Your agent starts from this guess that you provided. It then looks at the provided rewards, calculates if it will take a random action or not, and then selects a lever. $\endgroup$ Commented Jan 12, 2022 at 11:52

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.