View on GitHub

relearn

A Reinforcement Learning Library for C++11/14

Off-policy traces: off-policy TD(λ), Expected Sarsa(λ) and Tree-Backup(λ)

Eligibility traces (have a look at eligibility_traces.md) share every TD error with the steps that came before it. Off-policy, the steps were taken by a behaviour policy b, and the values to learn are those of another, the target policy π: a greedy one, say, learnt from an agent that explores. Each step then has to be weighted by how likely π was to take it. Sutton and Barto [1] give two ways of doing it with traces, in Sections 12.9 and 12.10, and relearn has both:

Watkins’s Q(λ) (eligibility_traces.md) is a third way, for a greedy π only: its traces are cut after every move that is not greedy.

Importance sampling, a step at a time

For state values, the λ-return of Section 12.9 weights what follows each state by its ratio, and keeps the value of the state for the rest of the weight:

G^{\lambda s}_t = \rho_t \left( r_t + \gamma_{t+1} \left( (1 - \lambda_{t+1}) \, V(s_{t+1}) + \lambda_{t+1} \, G^{\lambda s}_{t+1} \right) \right) + (1 - \rho_t) \, V(s_t)

where, as always, r_t is the reward received after leaving s_t (have a look at the reward convention), and γ_t = γ(s_t) and λ_t = λ(s_t, a_t) may vary from state to state (Section 12.8). The (1 - ρ_t) V(s_t) term is the control variate: a step π would never take (ρ_t = 0) leaves V(s_t) where it is. Its backward view, off-policy TD(λ), is TD(λ) with the ratio in the trace:

\delta_t = r_t + \gamma_{t+1} \, V(s_{t+1}) - V(s_t) \qquad z(s) \leftarrow \rho_t \left( \gamma_t \lambda_t \, z(s) + [s = s_t] \right) \qquad V(s) \leftarrow V(s) + \alpha \, \delta_t \, z(s)

For action values, the TD error is Expected SARSA’s, with V̄(s) = Σ_a π(a | s) Q(s, a), and the ratio fades the traces from the next step on, since Q(s_t, a_t) is already the value of the action taken:

\delta_t = r_t + \gamma_{t+1} \, \bar V(s_{t+1}) - Q(s_t, a_t) \qquad z(s, a) \leftarrow \gamma_t \lambda_t \rho_t \, z(s, a) + [s = s_t, a = a_t] \qquad Q(s, a) \leftarrow Q(s, a) + \alpha \, \delta_t \, z(s, a)

whose λ-return is

G^{\lambda a}_t = r_t + \gamma_{t+1} \left( (1 - \lambda_{t+1}) \, \bar V(s_{t+1}) + \lambda_{t+1} \left( \rho_{t+1} \, G^{\lambda a}_{t+1} + \bar V(s_{t+1}) - \rho_{t+1} \, Q(s_{t+1}, a_{t+1}) \right) \right)

Offline, if the values do not change during the episode, the TD errors add up to exactly the λ-return’s error, and the two make the very same changes; online, nearly. With λ = 0 both are one-step methods (Expected SARSA, for the action values), and with π = b every ratio is 1 and off-policy TD(λ) is TD(λ).

The traces can grow. A ratio is above 1 whenever π takes an action more often than b: with a greedy π and an agent that picks one of 4 moves at random, ρ = 4 at every greedy move, and the traces grow by γλρ at every step. With γ = 0.95 and λ = 0.9 that is 3.4, and in about half the runs the values blow up (see the example below); with λ = 0.25 it is 0.95, and they don’t. This is the variance of importance sampling (have a look at monte_carlo.md), a step at a time.

Tree-Backup(λ)

Tree backup weights each step by π alone. After each reward, it takes the values of the actions π might have taken instead, and carries on with the return of the action taken, each weighted by its probability:

G^{\lambda a}_t = r_t + \gamma_{t+1} \left( (1 - \lambda_{t+1}) \, \bar V(s_{t+1}) + \lambda_{t+1} \left( \sum_{a \neq a_{t+1}} \pi(a \mid s_{t+1}) \, Q(s_{t+1}, a) + \pi(a_{t+1} \mid s_{t+1}) \, G^{\lambda a}_{t+1} \right) \right)

Its backward view is the one above, with π(a_t | s_t) in place of ρ_t: the traces fade by γ_t λ_t π(a_t | s_t). Probabilities are at most 1, so the traces only ever shrink, and whatever b was, nothing blows up. The price is that they shrink even on-policy, whenever π is not close to deterministic, so tree backup looks less far ahead than its λ says. With a greedy π its traces are cut after a move that is not greedy, much as Watkins’s Q(λ)’s are.

When b is uniform, 1/k for each of k actions, the two are one: ρ_t = k π(a_t | s_t), so Tree-Backup(λ) is importance sampling with λ / k, exactly.

In relearn

// off-policy TD(λ): the state values of π, learnt from episodes played by b
auto pi = [](const state & s, const action & a) { return a.trait() == 0 ? 0.85 : 0.05; };  // π(a | s)
auto b  = [](const state & s, const action & a) { return 0.25; };  // b(a | s)
relearn::off_policy_td_lambda<state,action> td(0.02, 0.95, 0.5, pi, b);   // α, γ, λ, π and b
auto r = games::play(game, agent, 1000);
td(r.episode, r.terminated);
double v = td.value(s);
// off-policy Expected Sarsa(λ): π as a distribution (greedy if not set), and b
relearn::off_policy_expected_sarsa_lambda<state,action> sampled(0.1, 0.95, 0.25, nullptr, b);
sampled(r.episode, memory, r.terminated);
// Tree-Backup(λ): π alone (greedy if not set)
relearn::tree_backup_lambda<state,action> tree(0.1, 0.95, 0.9);
tree(r.episode, memory, r.terminated);

Example: FrozenLake from random play

examples/frozen_lake_off_policy.cpp learns slippery 4x4 FrozenLake (see examples/games/frozen_lake.hpp, γ = 0.95) from an agent that only ever moves at random, b = 1/4 for every move. The true values come from value iteration on the game’s model, frozen_lake::model(). First the optimal values q*, with a greedy π (the RMS error of Q, 20 runs):

    episodes:                                 100       1000      10000
    Expected SARSA (λ = 0)                 0.2814     0.2062     0.0487
    Watkins's Q(λ), λ = 0.9                0.2714     0.1837     0.0487
    Tree-Backup(λ), λ = 0.5                0.2809     0.1990     0.0470
    Tree-Backup(λ), λ = 0.9                0.2804     0.1912     0.0490
    Tree-Backup(λ), λ = 1                  0.2803     0.1888     0.0491
    importance sampling, λ = 0.25          0.2803     0.1888     0.0491
    importance sampling, λ = 0.9           0.2875     0.5250    59.4693

The traces help early on (after 1000 episodes), and Watkins’s Q(λ) and Tree-Backup(λ) end where Expected SARSA does. Tree-Backup(1) and importance sampling with λ = 0.25 learn the very same values (their largest difference is 0), as they should with a uniform b. And importance sampling with λ = 0.9 blows up in about half the runs, taking the mean error with it: its traces grow by 3.4 at every greedy move.

Then the state values of a policy that takes the optimal move with 0.85 and each other one with 0.05, with off-policy TD(λ) (α = 0.02, the RMS error of V, 20 runs):

    episodes:                                 100       1000      10000
    off-policy TD(λ), λ = 0.0              0.2587     0.2005     0.0311
    off-policy TD(λ), λ = 0.5              0.2555     0.1604     0.0417
    off-policy TD(λ), λ = 0.9              0.2594    69.7717    56.4070

With λ = 0.9, γλρ = 0.95 * 0.9 * 3.4 = 2.9 at every move π prefers, and in about half the runs the values blow up too.

The program succeeds if Tree-Backup(0.9) ends within 0.07 of q*, if Tree-Backup(1) and importance sampling with λ = 0.25 learn the same values to within 10⁻¹², if importance sampling with λ = 0.9 ends further than 1 away on average, and if off-policy TD(λ) ends within 0.08 of the true values with λ = 0 and 0.1 with 0.5, and further than 1 with 0.9. In 9 sets of 20 runs each, 11 to 14 runs of importance sampling with λ = 0.9 and 8 to 11 of off-policy TD(λ) with λ = 0.9 ended above 1, and the others did not blow up at all.

note: these numbers are GCC’s. With Clang’s standard library (libc++), whose random numbers differ, they are a little different, in the same order.

Tests

tests/off_policy_traces_test.cpp checks:

Each threshold of the tests was set from 10 seeds, with GCC’s standard library and with Clang’s (libc++).

References

  1. Sutton, R.S. and Barto, A.G., 2018. Reinforcement Learning: An Introduction, 2nd edition. Cambridge, MA: MIT Press. Section 7.5 (n-step tree backup), Section 7.6 (n-step Q(σ)), Section 12.8 (a λ and a γ that vary), Section 12.9 (off-policy traces with control variates), Section 12.10 (Watkins’s Q(λ) and Tree-Backup(λ)).
  2. Precup, D., Sutton, R.S. and Singh, S., 2000. Eligibility traces for off-policy policy evaluation. In Proceedings of the 17th International Conference on Machine Learning (ICML).