Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
"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. –  Erel Segal Halevi Dec 27 '12 at 14:53
    
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. –  Erel Segal Halevi Dec 27 '12 at 15:12
    
If $z_{t} = \frac{1}{t}$ then you have the index method anyway. –  Jeremy List Dec 29 '12 at 4:57
    
That's what I asked - Is it possible to prove, that the Q values converge to one of the indices given in the literature? –  Erel Segal Halevi Dec 29 '12 at 17:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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