5
$\begingroup$

I am interested in the stateless k-armed bandit problem, where an agent repeatedly chooses one of k independent arms, each with a different distribution of rewards, and tries to maximize its total reward.

I read many papers about this subject, but I am still confused, as there are two types of solutions:

A. It has been proven that the optimal solution to this problem is an index policy: For each arm, calculate a quality index, based on the rewards received from that arm so far. The index roughly estimates an upper confidence bound on the expected reward from that arm. Now choose the arm with the highest index.

B. On the other hand, this problem can also be presented as a Markov decision process, which can be solved by Q-learning. The general formula for Q-learning is:

$Q_{t+1}(s,a) := (1-z_t) Q_t(s,a) + z_t (R_t + g * max_{a'}(Q_t(s',a'))$

Where: t is the time, s is the state we were at, a is the action we did, s' is the state we got into, $z_t$ is the rate of learning at time t, R_t is the reward we received at time t, and g is a constant discount rate.

In this case, there is only a single non-terminal state. Each arm-pull is an episode: it starts with the initial state, and always goes to the final state. Therefore, the Q value of the final state is always 0, and we only need to calculate Q values for actions of the single initial state:

$Q_{t+1}(a) := (1-z_t) Q_t(a) + z_t R_t$

It is guaranteed that the process will converge to an optimal policy, if each action is selected eventually, and if the learning rate $z_t$ decreases in an appropriate rate (speficically, $\sum_{t=1}^\infty z_t^2 < \infty$ and $\sum_{t=1}^\infty z_t = \infty$).

Now, my question is: what is the relation between two methods for solving the k-armed bandit problem?

  1. Is it possible to prove, that the Q values converge to one of the indices given in the literature?

  2. Why use an index method, if it is possible to use the much simpler Q-learning method?

$\endgroup$

1 Answer 1

1
$\begingroup$

The difference between your formula and the index methods is that your formula gives more weight to recent data. If there's a lever that has large but infrequent rewards then your formula won't converge.

On the other hand, your formula will perform better than index methods if the reward distribution for some of the levers changes across time.

The next state is actually not the terminal state unless there are no more trials, so simplifying out $g * max_{a'}Q_{t}(s',a')$ is only valid if $g = 0$. But in this case $g = 0$ should work quite well.

$\endgroup$
4
  • $\begingroup$ "The difference between your formula and the index methods is that your formula gives more weight to recent data" - I related to this in my recent edit - Q-learning converges when the rate of learning, $z_t$, decreases in an appropriate rate, so that the weight of new information decreases with time. $\endgroup$ Dec 27, 2012 at 14:53
  • $\begingroup$ I define the MDP such that each arm-pull is an episode, with only a single step - starts with the initial state, pulls a lever, and gets to the terminal state. In Q-learning, there are many episodes, so there are many trials, but each episode has a single step. So, the Q value of the terminal state is always 0, regardless of g. $\endgroup$ Dec 27, 2012 at 15:12
  • $\begingroup$ If $z_{t} = \frac{1}{t}$ then you have the index method anyway. $\endgroup$ Dec 29, 2012 at 4:57
  • $\begingroup$ That's what I asked - Is it possible to prove, that the Q values converge to one of the indices given in the literature? $\endgroup$ Dec 29, 2012 at 17:20

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.