2
$\begingroup$

When using Bellman equation to update q-table or train q-network to fit to greedy max values, the q-values very often get to the local optima and get stuck although randomisation rate ($\epsilon$) already applied since start.

The sum of q-values of all very first steps (of different actions at the original location of agent) increases gradually until a local optimum is reached. It gets stuck and this sum of q-values starts decreasing slowly a bit by a bit.

How to avoid being stuck in a local optimum? and how to know if the local optimum is already the global optimum? I may think of this but it's chaotic: Switch on randomisation again for a while, worse values may come at first but may be better in future.

$\endgroup$
1
$\begingroup$

I found out the problem why the optimisation process got stuck and never moved closer to global optimum. It's because of the rate between 'explore' or 'exploit'.

Basically, in RL, agent 'explore's by doing a random action and to find new solutions, 'exploit's the existing so-called known max future rewards to do the max action.

Initially, I put the agent to explore when $random() < 1/(replay\_index+1)$, exploration rate reduces too quick (<10% after 10 iterations), and when the number of replays (number of times to play again from start) is not enough, the explore rate at the end of the loop is almost zero, and nothing new learnt.

The solution opted is allowing 'explore' and 'exploit' have the same rate (or lower exploration a bit is also ok), pseudo-code:

# Part 1 in a step: Choose action
if random() < 0.5: # 0.25 is also good, 25% for exploration
    action = random_action()
else:
    action = choose_best_known_action()

Explore rate can be reduced correctly this way:

if random() < 1-i/NUM_REPLAYS: # i is current train step index
    action = random_action()
else:
    ...

With the half-explore/half-exploit scheme above, the agent will learn to infinity, so, it is kinda sure that global optimum would be reached. When knowing from practice the number of iterations should be used, 'exploit' may be utilised more for faster convergence.

Note that the 'explore' and 'exploit' rates are put equal above, the but q-table or q-network is still better and better due to having another 'exploit'-kind when updating q-table or fitting q-network with Bellman equation, there's another 'exploit' here, the 'max' in Bellman equation:

Pseudo-code:

# Part 2 in a step: Update q-table or q-network
q[s][a] += learning_rate * (reward + max(q[sNext][aNext]) - q[s][a])

# Q-network
# target = r + max(...
```
$\endgroup$
3
  • 1
    $\begingroup$ what do you mean with "when the number of replays (number of times to play again from start) is not enough"? $\endgroup$
    – malioboro
    Mar 17 at 10:49
  • $\begingroup$ it's the outer most interation, RL plays from square 1, again and again a 'number of replays' $\endgroup$ Mar 17 at 10:54
  • $\begingroup$ not enough replays --> not enough iterations (the outer most loop) $\endgroup$ Mar 17 at 12:17

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.