Understanding advantage functions

Question

The paper explaining 'Advantage Updating' as a method to improve Q-learning uses the following as its motivation.

Q-learning requires relatively little computation per update, but it is useful to consider how the number of updates required scales with noise or with the duration of a time step, At. An important consideration is the relationship between Q values for the same state, and between Q values for the same action. The Q values Q(x,u1) and Q(x,u2) represent the long-term reinforcement received when starting in state x and performing action u1 or u2 respectively, followed by optimal actions thereafter. In a typical reinforcement learning problem with continuous states and actions, it is frequently the case that performing one wrong action in a long sequence of optimal actions will have little effect on the total reinforcement. In such a case, Q(x,u1) and Q(x,u2) will have relatively close values. On the other hand, the values of widely separated states will typically not be close to each other. Therefore Q(x1,u) and Q(x2.u) may differ greatly for some choices of x1 and x2. Therefore, if the network representing the Q function makes even small errors, the policy derived from it will have large errors. As the time step duration dt approaches zero, the penalty for one wrong action in a sequence decreases, the Q values for different actions in a given state become closer, and the implied policy becomes even more sensitive to noise or function approximation error. In the limit, for continuous time, the Q function contains no information about the policy. Therefore, Q-learning would be expected to learn slowly when the time steps are of short duration, due to the sensitivity to errors, and it is incapable of learning in continuous time. This problem is not a property of any particular function approximation system; rather, it is inherent in the definition of Q values.

How do I mathematically prove that this effect occurs?

Answer 1

1. Why are the q-values of different actions very close to each other for a given state ?

I'm going to explain this with a small example.

Consider the game of "Catch". Fruits(circular) keep falling from the top of the screen (vertically) and the agent(square) needs to just align itself to the fruit to get the reward. There are three actions that it can take : move left , stay , move right. Let's say that a2 refers to not moving the paddle, a3 refers to moving right and a1 refers to moving left. The image on the screen is to be used as the state in the MDP formalism.

Let's say we take a sub-optimal action a3(move right) and move to the next state. Then the best action in that state would be to move left (a1) and then execute the optimal action. So, the only cost difference between the actions a2 and a3 will be the two steps wasted to go and come back.

If there is no negative reward for taking the sub-optimal action, then the agent has no incentive to choose the optimal action. So, the negative rewards for taking the sub-optimal action should be high enough that the agent is discouraged from doing it. I've tried to put this intuition mathematically here. This could explain why q-values are so close to each other.

Then, the optimal Q* function satisfies the following :

2. Is there a bound on this gap ? The bound that I've shown is approximate. The technical term for this difference is "Action Gap". A much better analysis is available here : Increasing the Action Gap: New Operators for Reinforcement Learning

3. Why are the q-values of different states very close to each other for a given action ?

This should be fairly obvious. Consider two different cases. In the first one, the fruit falls from the top left corner and in the second one, the fruit falls from the top right corner. The agent in both cases is at the center. Then, consider the action of moving left. This action will give a high q-value in the first case and a low q-value in the second case.

4. How to solve the action gap problem ?

Let's define the average reward in a state to be $V$. $V$ is approximately the average of Q-values of all the actions in a given state. If we now subtract this $V$ from each of the $Q$ values, we get a quantity which describes how good the action is compared to the average of all the action. This is called as the advantage of the action. In some sense, this is approximately the action gap. So, instead of predicting the q-values, we are directly predicting the action gap itself.

Link : A3C paper