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... ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,