2
$\begingroup$

When considering multi-armed bandits in different formats, UCB, $\epsilon$-greedy, thompson sampling etc seems so greedy/myopic in the sense that it solely considers reward for the current timestep.

To be more precise, why dont we consider the information we gain by exploration and how this will affect us in future timesteps when making future decisions. More specifically, shouldnt it be better to try to quantify the value of information from exploratory actions and model this over a longer horizon..

I.e, why dont we model this as a MDP and use (approximate)dynamic programming techniques?

In that sense we might see that playing arm $x$ now will lead us to this information, which in turn will lead to this and so on.

I must have missed out on some literature/techniques.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The (binary) multi-armed bandit actually is a MDP with one state and $K$ actions.

So your suggestion boils down to meta-learning: Find the parameters of one MDP that can solve another. Let's go with that!

So we need to specify this meta-MDP. To simplify, we make it solve Bernoulli (binary) multi-armed Bandits.

What state would this meta-MDP use?

  • The full history of actions and rewards? One state would be [(A-1), (A-0), (C-0), (B-1), (B-1), (B-1)], Clearly this has redundant information. Because the bandit is stateless, the order in which we tried the arms is irrelevant for the optimal decision about the next action (which arm to try).

  • Same as above, but ignoring order? That boils down to counting. One state would be {A: (1,1), B: (0,3), C: (1,0), D: (0,0)}. The number of states is infinite. But if we limit ourselves to a few steps, we could totally simulate this meta-MDP.

If we actually wanted to optimize this meta-MDP:

  • We would have to specify the distribution of Bandits we want to be optimal for.
  • We may want to specify a time-horizon. (Or the discounting of future rewards that we want to be optimal for.)
  • We may notice more symmetry that we haven't exploited yet: If the optimal action in the state above is A, the surely in the state where A/B are swapped it should be B.

Back to your question:

Why dont we consider the information we gain by exploration? I.e, why dont we model this as a MDP?

We have almost done this now! We could optimize the meta-MDP above and extract the optimal policy. The optimal policy is of course a deterministic function from state to action.

Let's cross-check what the UCB algorithm (PDF) does: In the first $K$ rounds, where $K$ is the number of arms, play each arm once, in arbitrary order. [...]

Wait, this specifies what action our optimal policy should take for some of the states! If we read further, we can find the action for other states too. This is a policy!

So another way to think about UCB (or Thomson Sampling, or even $\epsilon$-greedy) is that they are actually specific policies/solutions for the above meta-MDP.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ my question was not really clear, i was more getting at information state space algorithms and the value of information, i.e if we know the value of information we can trade-off exploration and exploitation optimally, see 1:09:06 youtube.com/… $\endgroup$
    – hugh
    Sep 27 at 7:19
  • $\begingroup$ however, i'll accept this answer as the question was not really clear. I'll will create a new question however... $\endgroup$
    – hugh
    Sep 27 at 7:20
  • $\begingroup$ new thread: ai.stackexchange.com/questions/42218/… $\endgroup$
    – hugh
    Sep 27 at 7:33
  • $\begingroup$ The maximally greedy algorithm would always choose the action with highest expected reward. Neither UCB, nor Thompson Sampling nor even $\epsilon$-greedy (with $\epsilon > 0)$ try to be optimal for such a short time-horizon. Maybe you have a misconception there, or maybe I still don't understand your question, sorry about that :) $\endgroup$
    – maxy
    Sep 27 at 14:35

You must log in to answer this question.