2
$\begingroup$

I'm trying to implement a temporal difference algorithm that learns the maximum revenue over a period of time using prices as the actions, inventory as the state, and revenues realized as the reward. The problem I'm having is that I can't seem to get it to converge on an optimal policy. It seems like it gets stuck at a revenue somewhere around 60% of optimization and then won't budge anymore. Are there some common pitfalls that might be causing this? I've tried playing with the rate of exploration a little bit, but that hasn't seemed to help it much.

EDIT: Ok, so I went back through everything, and it seems like the problem is that, when it stops exploring, it just keeps increasing the Q-values of states that it's already deemed the best in the past. So for example, it visits the price 5 at a certain state and time and gets a reward. Then, in the next several episodes, it continues to visit 5, and continues getting a reward, adding that reward to the Q-value until it's pretty high. At that point, even if it were to explore at the same state and time, the reward it gets isn't enough to overcome the inflated Q-value, so it just goes right back to 5 in the next episode. Here are the steps I'm trying to follow.

$\endgroup$
1
$\begingroup$

Sounds like an interesting application. To debug RL applications, I like to perform rollouts. First identify a state where the current policy appears to be clearly wrong; (maybe sample some states and look at them individually). Then switch off the learning and run a sample from that state for both the current RL policy and the action you think is correct. This should give you the true action values. Hopefully, that will give you a hint as to what's going wrong. If it's an exploration problem, then the current policy won't be trying any actions similar to the action you think is correct. If the form of the value function is wrong, then it won't fit the values coming from your samples.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I edited my findings into the question, I'm not sure if it notifies you of that or not. $\endgroup$ – user3704120 Jul 9 '15 at 12:50
  • 1
    $\begingroup$ Maybe use some "optimism bias". Initialize all Q-values above any reasonable estimate of their long run value. Then states that haven't been tried will always have Q-values above those that have and this encourages exploration. $\endgroup$ – nsweeney Jul 9 '15 at 13:11
  • 1
    $\begingroup$ I tried initializing the Q-values a couple different ways with no success. Let me see if I'm understanding the update process correctly: ∀ $i≤ t ∈ T$, ∀ $x_i$, $a_i$ Update all Q-Values according to their eligibility traces $Q_t^{k+1}(x_i, a_i) ← Q_i^k(x_i, a_i) + α(x_i^k,a_i^k)δ_t^ke_t^k(x_i,a_i)$ $\endgroup$ – user3704120 Jul 10 '15 at 1:06
  • $\begingroup$ So essentially what this is saying is that the Q value for the time period that I'm in during the next episode will be equal to the current Q value + learning rate * TD error * eligibility trace for all state-action pairs that I've visited during this episode, correct? $\endgroup$ – user3704120 Jul 10 '15 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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