Value-based (and Q-) Learning

Value Function / Q Function Fitting (Value-Based)

Can we omit policy gradient completely from actor-critic methods?

Actor-critic minimizes

But the best policy can just be extracted from $\argmax_{a_t} A^{\pi}(s_t,a_t)$

We know that $\pi '$ is as good as $\pi$, and probably better.

Same as before,

Policy Iteration (Fitted Value Iteration)

So fitting value function can be done if we know the transition dynamics very easily using least square estimate… but what if we don’t know transition dynamics?

Policy Iteration without transition probability (Fitted Q-Iteration)

What if we change the policy evalution part to

Now ⇒ if we have an $(s,a,r,s’)$ tuple then even if policy $\pi '$ changes its action in state $s$ we can still do policy evalution on the tuple because the only place the policy shows up is inside the expectation.

This simple change allows us to policy iteration style algorithms without actually knowing the transition dynamics

Instead of using $\mathbb{E}[V(s_i)]$, we used $\max_{a’} Q_\phi(s_i’,a_i’)$, the value function $V(s_i)$ is approxiamted by $\max_{a’} Q_\phi(s_i,a’)$ and intead of doing expectations on the future possible states, we used the next state in the sample $s_i’$

• Works for off-policy samples

• Only one network, no high-variance policy gradient

• No convergence guarentees for non-linear function approximation (more on this later)

Special Cases of Fixed Q-Fitting

During exploration phase, using the greedy algorithm may not be the optimal choice (we want to maximize entropy!)

“Epsilon Greedy”

“epsilon chance of exploring other options other than optimal action”

Common practice is to vary epsilon while training (early on(Q is bad), larger epsilon)

“Exponential”

Best action will be most frequent, but leave some probability for exploration. And plus, if there is a second largest Q, then this second largest is considered more than other options.

Value Function Learning Theory

For tabular value iteration algorithm:

The Bellman Operator encaptures the logic of updating $V(s)$

And one fact is that:

$V^*$, the value function for the optimal policy, is a fixed point of $B$

$V^*$ always exists, is always unique, and always corresponds to the optimal policy

Does fixed point iteration converge to $V^*$

We can prove that the value iteration reaches $V^*$ because $B$ is a contraction

Contraction means: for any $V$ and $\bar{V}$, we have $||BV-B\bar{V}||_\infin \le \gamma||V-\bar{V}||_\infin$ where $\gamma \in (0,1)$

Meaning that $V$ and $\bar{V}$ will get closer and closer as we apply $B$ to them

If we replace $\bar{V}$ by $V^*$ (and since $BV^* = V^*$),

For fitted value iteration algorithm:

Step 1 basically applies the bellman operator

We will define a new operator for step 2, $\Pi$ (pi)

Step 2 performs the following:

“Find an value function in the value function model hypothesis space $\Omega$ that optimizes the objective”

So step 2 performs this model fitting operator $\Pi$ that projects $BV$ onto hypothesis space $\Omega$, our iteration algorithm can now be described as

$B$ is still a contraction with respect to $\infin$ norm

$\Pi$ is a contraction wr.t. L2-norm

However, $\Pi B$ is not a contraction of any kind

So fitted value iteration does not converge in general and often does not converge in practice

Same with fitted Q-Iteration, Batch actor-critic

But why? Isn’t value function fitting just graident descent?

We can actually turn this into a gradient descent algorithm by computing into those target functions ⇒ resulting algorithm is called residual algorithms, has poor numerical properties & doesn’t work well in practice

Correlation Problem in Q-Learning

Think about a sequence

In the early 3 steps, the target value is kind of “overfit” to those 3 values

In the supervised setting of learning Q / Value functions, the data points seen by the target values are only local states

We can solve this by adding more batches at one time (by synchronized parallel Q-learning or asynchronous parallel Q-learning)

Or we use replay buffers (Since fitted Q-Learning is basically a off-policy method) ⇒ Samples are no longer correlated and multiple samples in the batch (low-variance gradient)

But where does the data come from:

1. Need to periodically feed the replay buffer

Maybe just move one gradient step instead

Usually ⇒ $K \in [1, 4]$, $N \in [10000, 50000]$

Target network makes sure that we’re not trying to hit a moving target ⇒ and now it looks more like supervised regression

Question: Chasing its tail relationship, is there a typical scenerio where Q function chases its tail and shows bad behaviors?

Classic Deep Q-Learning Algorithm (DQN)

A special case(with specific parameters) of Q-learning with replay buffer and target network

A general view of Q-Learning

Online Q-learning (last lecture): evict immediately, process 1, process 2, and process 3 all run at the same speed.

DQN: Process 1 and process 3 run at the same speed, process 2 is slow.

Fitted Q-iteration: process 3 in the inner loop of process 2, which is in the inner loop of process 1

Overestimation in Q-Learning and Double Q-Learning

Because target value

Imagine two r.v. $X_1, X_2$

We can prove:

But:

$Q_{\phi '}(s',a')$ is not perfect, it is “noisy” ⇒ We are always selecting the positive errors while training using the $\max$

Note that

So use “double Q-Learning” ⇒ use two networks

Update $\phi A$ by using $\phi B$ as a target network and $\phi A$ as an action selector, opposite with $\phi B$ update.

Intuition: Choosing the “optimal” (but due to noise) action in $Q_{\phi A}$ will cause the noise of the same action in $Q_{\phi B}$ to be added into the result, therefore the “overestimation” effect is mitigated

In practice, instead of having two Q functions, use the two Q functions that we already have.

We already have $\phi$ and $\phi '$

In standard Q-learning:

Double Q-Learning:

Multi-step returns

Q-learning target

Early on in training, the term $\gamma \max_{a_j, t+1} Q_{\phi ‘}(s_{j,t+1},a_{j,t+1})$ only gives us random noise if the network is bad, so $r_{j,t}$ is the most important. But later in training, when $Q_{\phi'}$ gets better and better, this term dominates(since we have more terms then just a single term reward) and is more important.

So we can have something like “Monte Carle” sum of rewards in Actor-Critic algorithms

1. Higher variance

2. but lower bias
   1. Faster learning especially early on

3. but only correct when on-policy learning
   1. In the second step it actually matters what action you take because the exploration policy might be different from current policy

How to fix the “on-policy” limit?

1. Ignore the problem (😂 Yeah this is SOOOO CS)
   1. Often works very well

2. Cut the trace
   1. dynamically choose N to get only on-policy data
   2. Works well when data mostly on-policy, and action space is small

3. Importance sampling
   1. “Safe and efficient off-policy reinforcement learning. “ Munos et al. ‘16

Extending Q-Learning to continuous action space

Problem with continuous actions:

1. Our policy has to select $\argmax Q_\phi$

2. When evaluting the $y_j$ for training $Q_\phi$ we also need to $\argmax$
   1. Particularly problematic(since this runs in a loop!）

Options:

1. Continuous Optimization Procedure
   1. Gradient based optimization (like SGD) is a bit slow in the inner loop
   2. Action space typically low-dimensional ⇒ So no need to do gradient optimization

2. Stochastic optimization
   1. Uses the fact that action space is low-dimensional (easy to solve for optima)

3. Use a function class that is easy to optimize
   1. Quadratic function?
      1. Gu, Lillicrap, Sutskever, L., ICML 2016
         1. Normalized Advantage Functions (NAF) architecture
   2. No change to algorithm
   3. Just as efficient as Q-Learning
   4. But loses representational power

4. Learn an approximate maximizer
   1. Learn a function maximizer using neural nets
   2. DDPG (Lillicrap et al. ICLR 2016)
      1. “Deterministic” actor-critic (really approximate Q-Learning)
      2. $\max_{a} Q_{\phi} (s,a) = Q_\phi (s, \argmax_a Q_\phi (s,a))$
         1. Idea is to train another network $\mu_\theta(s)$ such that $\mu_\theta(s) \approx \argmax_a Q_{\phi}(s,a)$
         2. $\frac{dQ_\phi}{d\theta} = \frac{da}{d\theta} \frac{d Q_{\theta}}{da}$
   3. classic: NFQCA
   4. recent: TD3 and SAC

Stochastic Optimization

Simple Solution

Where $(a_1, \dots, a_N)$ are sampled from some distribution (e.g. uniform)

1. Dead simple

2. Efficiently parallelizable

3. But - not very accurate

More accurate (works OK for ≥ 40 dims):

1. Cross-entropy method (CEM)
   1. simple iterative stochastic optimization
   2. sampling actions from distribution like in the simple method but then refines to a range and then continues to sample in a smaller and smaller range

2. CMA-ES
   1. substantially less simple iterative stochastic optimization

Implementation Tips

1. Q-learning takes some care to stabilize
   1. Test on easy, reliable tasks first, make sure the implementation is correct
   2. Large replay buffers help improve stability
      1. Looks more like fitted Q-iteration
   3. Takes time, be patient - might be no better than random for a while
   4. Start with high exploration (epsilon) and gradually reduce
   5. Bellman error gradients can be big; clip gradients or use Huber loss

2. Double Q-learning helps a lot in practice
   1. Simple & no downsides!

3. N-step returns also help a lot
   1. but have some downsides (will systematically bias the objective)

4. Schedule exploration (high to low) and learning rates (high to low), Adam optimizer can help too

5. Run multiple random seeds, its very inconsistent between runs

Suggested Readings

1. Classic papers
   1. Watkins. (1989). Learning from delayed rewards: introduces Q-learning
   2. Riedmiller. (2005). Neural fitted Q-iteration: batch-mode Q-learning with neural networks

2. Deep reinforcement learning Q-learning papers
   1. Lange, Riedmiller. (2010). Deep auto-encoder neural networks in reinforcement learning: early image-based Q-learning method using autoencoders to construct embeddings
   2. Mnih et al. (2013). Human-level control through deep reinforcement learning: Q- learning with convolutional networks for playing Atari.
   3. Van Hasselt, Guez, Silver. (2015). Deep reinforcement learning with double Q-learning: a very effective trick to improve performance of deep Q-learning.
   4. Lillicrap et al. (2016). Continuous control with deep reinforcement learning: continuous Q-learning with actor network for approximate maximization.
   5. Gu, Lillicrap, Stuskever, L. (2016). Continuous deep Q-learning with model-based acceleration: continuous Q-learning with action-quadratic value functions.
   6. Wang, Schaul, Hessel, van Hasselt, Lanctot, de Freitas (2016). Dueling network architectures for deep reinforcement learning: separates value and advantage estimation in Q-function.