Making a Difference Tempore: Insights from 'Reinforcement Learning: An Introduction'

TurnTrout

The safety of artificial intelligence applications involving reinforcement learning is a topic that deserves careful attention.

Foreword

Let's get down to business.

Reinforcement Learning

1: Introduction

2: Multi-armed Bandits

Bandit basics, including nonstationarity, the value of optimism for incentivizing exploration, and upper-confidence-bound action selection.

Some explore/exploit results are relevant to daily life - I highly recommend reading Algorithms to Live By: The Computer Science of Human Decisions.

3: Finite Markov Decision Processes

The framework.

4: Dynamic Programming

Policy evaluation, policy improvement, policy iteration, value iteration, generalized policy iteration. What a nomenclative nightmare.

5: Monte Carlo Methods

Prediction, control, and importance sampling.

Importance Sampling

After gathering data with our behavior policy $b$ , we then want to approximate the value function for the target policy $π$ . In off-policy methods, the policy we use to gather the data is different from the one whose value $v_{π}$ we're trying to learn; in other words, the distribution of states we sample is different. This gives us a skewed picture of $v_{π}$ , so we must overcome this bias.

If $b$ can take all of the actions that $π$ can (i.e., $\forall a, s : π (a | s) > 0 ⟹ b (a | s) > 0$ ), we can overcome by adjusting the return $G_{t}$ of taking a series of actions $A_{t}, \dots, A_{T - 1}$ using the importance-sampling ratio $ρ_{t : T - 1} := \prod_{k = t}^{T - 1} \frac{π (A_{k} | S_{k})}{b (A_{k} | S_{k})}$ . This cleanly recovers $v_{π}$ by the definition of expectation:

\begin{matrix} ρ_{t : T - 1} E_{b} [G_{t} | S_{t} = s] & = (T - 1 \prod k = t \frac{π (A_{k} | S_{k})}{b (A_{k} | S_{k})}) E_{b} [G_{t} | S_{t} = s] = E_{π} [G_{t} | S_{t} = s] = v_{π} (s) . \end{matrix}

Then after observing some set of returns (where ${G_{t}}_{t \in T (s)}$ are the relevant returns for state $s$ ), we define the state's value as the average adjusted observed return

V (s) := \frac{\sum_{t \in T (s)} ρ_{t : T (t) - 1} G_{t}}{| T (s) |} .

However, the $ρ_{t : T (t) - 1}$ 's can be arbitrarily large (suppose $π (A | S) = .5$ and $b (A | S) = 1 \times 10^{- 10}$ ; $\frac{.5}{1 \times 10^{- 10}} = .5 \times 10^{10}$ ), so the variance of this estimator can get pretty big. To get an estimator whose variance converges to 0, try

V (s) := \frac{\sum_{t \in T (s)} ρ_{t : T (t) - 1} G_{t}}{\sum_{t \in T (s)} ρ_{t : T (t) - 1}} .

Death and Discounting

Instead of viewing the discount factor $γ$ as measuring how much we care about the future, think of it as encoding the probability we don't terminate on any given step. That is, we expect with $1 - γ$ probability to die on the next turn, so we discount rewards accordingly.

This intuition hugs pre-theoretic understanding much more closely; if you have just 80 years to live, you might dive that big blue sky. If, however, you imagine there's a non-trivial chance that humanity can be more than just a flash in the pan, you probably care more about the far future.

6: Temporal-Difference Learning

The tabular triple threat: $TD(0)$ , $SARSA$ , and $Q$ -learning.

Learning TD Learning

V (S_{t}) \leftarrow V (S_{t}) + α [TD target      R_{t + 1} + γ V (S_{t + 1}) - V (S_{t})      TD error]

$_{TD(0)} ⋆_{Q}^{SARSA}$

$TD(0)$ is one-step bootstrapping of state values $v_{π}$ . It helps you learn the value of a given policy, and is not used for control.
$SARSA$ is on-policy one-step bootstrapping of action values $q_{π}$ using the quintuples $(S, A, R, S^{'}, A^{'})$ .

As in all on-policy methods, we continually estimate $q_{π}$ for the policy $π$ , and at the same time change $π$ toward greediness with respect to $q_{π}$ .

33