3
$\begingroup$

I am trying to understand how to make sure that our agent explores the state space enough before exploiting what it knows. I am aware that we use epsilon-greedy approach with a decaying epsilon to achieve this. However I came across another concept, that of using exploration functions to make sure that our agent explores the state space.

Q Learning with Epsilon Greedy


$sample = R(s,a,s') + \gamma \max_{a'}Q(s',a')$
$Q(s,a) = (1 - \alpha)*Q(s,a) + \alpha*sample$

Exploration function

$ f(u,n) = u + k/n $
$Q(s,a) = R(s,a,s') + \gamma*max_{a'}f(Q(s',a'), N(s',a'))$
Where N(s',a') counts the number of times you have seen this (s',a') pair before.


Now my question is, are these 2 above strategies just 2 different ways of Q learning? Because I can't seem to find much details on exploration function but can find plenty on epsilon greedy Q learning. Or can the exploration function be used along with the epsilon greedy Q learning algorithm as a form of some optimization? I am confused as to where exactly would we make use of this exploration function Q learning strategy. Any help/suggestions are much appreciated!

$\endgroup$
3
$\begingroup$

Any exploration function that ensures the behaviour policy covers all possible actions will work in theory with Q learning. By covers I mean that there is a non-zero probability of selecting each action in each state. This is required so that all estimates will converge on true action values given enough time.

As a result, there are many ways to construct behaviour policies. It is possible in Q learning to use equiprobable random action choice - ignoring current Q values - as a behaviour policy, or even with some caveats learn from observations of an agent that uses an unknown policy.

There are practical concerns:

  • If the behaviour policy is radically different from optimal policy, then learning may be slow as most information collected is not relevant or very high variance once adjusted to learning the value of the target policy.

  • When using function approximation - e.g. in DQN with a neural network - the distribution of samples of state, action pairs seen has an impact on the approximation. It is desirable to have similar population of input data to that which the target policy would generate*.

  • In some situations, a consistent policy over multiple time steps gives better exploration characteristics. Examples of this occur when controlling agents navigating physical spaces that may have to deviate quite far from current best guess at optimal in order to discover new high value rewards.

These concerns drive designs of different exploration techniques.

The epsilon-greedy approach is very popular. It is simple, has a single parameter which can be tuned for better learning characteristics for any environment, and in practice often does well.

The exploration function you give attempts to address the last bullet point. It adds complexity, but may be useful in a non-stationary environment since it encourages occasional exploration paths far away from the current optimal one.

Now my question is, are these 2 above strategies just 2 different ways of Q learning?

Yes.

Or can the exploration function be used along with the epsilon greedy Q learning algorithm as a form of some optimization?

Yes it should be possible to combine the two approaches. It would add complexity, but it might offer some benefit in terms of learning speed, stability or ability to cope with non-stationary environments.

Provided the behaviour policy covers all possible actions over the long term, then your choice of how exploration for off-policy reinforcement learning works is one of the hyperparameters for a learning agent. Which means that if you have an idea for a different approach (such as combining two that you have read about), then you need to try it to see if it helps for your specific problem.


* But not necessarily identical, because the approximate Q function would then lose learning inputs that differentiate between optimal and non-optimal behaviour. This can be a tricky balance to get right, and is an issue with catastrophic forgetting in reinforcement learning agents.

$\endgroup$

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.