RL Theory

What is the point:

1. Prove that our RL algorithms will work perfectly every time
   1. Usually not possible with current deep RL methods, which are often not even guarenteed to converge

2. Understand how errors are affected by problem parameters
   1. Do larger discounts work better than smaller ones?
   2. If we want half the eror, do we need 2x the samples, 4x, or something else?
   3. Usually we use precise theory to get imprecise qualitative conclusions about how various factors influence the performance of RL algorithms under strong assumptions, and try to make the assumptions reasonable enough that these conclusions are likely to apply to real problems (but they are not guarenteed to apply to real problems)

Exploration

Performance of RL is greatly complicated by exploration - how likely are we to find potentially sparse rewards?

Theoretical guarantees typically address worst case performance ⇒ but worst case exploration is extremely hard

• If we “abstract away” exploration, how many samples do we need to effectively learn a model or value function that results in good performance?
  • “generative model” assumption: assume we can sample from $P(s’|s,a)$ for any $(s,a)$
  • “oracle exploration” assumption: For every $(s,a)$, sample $s’ \sim P(s’|s,a)$ N times

Basic Sample Complexity Analysis

RL Theory Textbook. Agarwal, Jiang, Kakade, Sun.

“Oracle Exploration”: for every $(s,a)$, sample $s’ \sim P(s’|s,a)$ N times

Simple “model-based” algorithm

1. $\hat{P}(s’|s,a) = \frac{\#(s,a,s’)}{N}$
   1. Count number of transitions

2. Given $\pi$, use $\hat{P}$ to estimate $\hat{Q}^\pi$

3. We want to measure worst case performance
   1. How close is $\hat{Q}^\pi$ to $Q^\pi$?
   2. How close is $\hat{Q}^*$(optimal function learned under $\hat{P}$) to $Q^*$(optimal function learned under real $P$)?
   3. How good is the resulting policy?

“How close is $\hat{Q}^\pi$ to $Q^\pi$?”

“How close is $\hat{Q}^*$ to $Q^*$?”

“How good is the resulting policy?”

Concentration Inequalities

How fast our estimate of random variable converges to the true underlying value (in terms of # of samples)

Hoeffding’s Inequality (For continuous distributions)

Suppose $X_1, \dots, X_n$ are a sequence of independent, identically distributed (i.i.d.) random variables with mean $\mu$. Let $\bar{X_n} = n^{-1}\sum_{i=1}^n X_i$. Suppose that $X_i \in [b_{-},b_{+}]$ with probability $1$, then

Therefore if we estimate $\mu$ with $n$ samples the probability we’re off by more than $\epsilon$ is at most $2 \exp \{ \frac{2n\epsilon^2}{(b_{+}-b_{-})^2} \}$ (since we can be off on both sides). So if we want this probability to be $\delta$:

Concentration for Discrete Distributions

Let $z$ be a discrete random variable that takes values in $\{1, 2, \dots, d \}$, distributed according to $q$. We can write $q$ as a vector where $\vec{q} = [\mathbb{P}(z=j)]_{j=1}^d$. Assume we have $N$ iid samples, and that our empiraical state of $\vec{q}$ is $[\hat{q}]_j = \sum_{i=1}^N 1\{z_i=j\} / N$

We have that $\forall \epsilon > 0$,

Which implies:

Let

Then

Using concentration inequalities, we see that in the “Basic Sample Complexity Analysis”, the state transition estimation difference is

Now: Relate error in $\hat{P}$ to error in $\hat{Q}^\pi$

Recall:

So if we write out the transition fuction $P$, the Q function $Q^\pi$, reward function $r$, and value function $V^\pi$ as matrices:

Remember that $V$ function is just an expectation over the $Q$ function (a sum) ⇒ so we can also write it as an expectation (where $\Pi \in \mathbb{R}^{|S| \times (|S||A|)}$ and is a probability matrix)

With this, (and $P^\pi = P \Pi$)

So

And turns out the matrix $(I - \gamma P^\pi)$ is always gonna be invertible

Simulation Lemma:

Proof:

Another Lemma:

Given $P^\pi$ and any vector $\vec{v} \in \mathbb{R}^{|S||A|}$, we have

“Q function” corresponding to “reward” $\vec{v}$ is at most $(1-\gamma)^{-1}$ times larger

Where does this $(1-\gamma)^{-1}$ come from? Geometric series of $\sum_{t=0}^\infin \gamma^t c = \frac{c}{1-\gamma}$

Let

Then

Putting the lemmas together,

Let the special case $\vec{v} = \gamma(P-\hat{P})V^\pi$

We can bound $||V^\pi||_\infin$

With this bound,

With the previous bound on

We conclude:

What about $||Q^* - \hat{Q}^*||_\infin$?

Supremium - lower upper bound of a function (greatest value of a function), one useful identity

And

What about $||Q^* - Q^{\hat{\pi}^*}||_\infin$?

Fixed Q-Iteration

Abstract model of exact Q-iteration

Abstract model of approximate fitted Q-iteration:

Where $\hat{T}$ is the approximate bellman operator:

Note: We will not be computing $\hat{P}$ and $\hat{r}$, it would just be the effect of averaging together transitions in the data (having different gradients for different samples)

We will assume an infinity norm here because there will be no convergnce if using L2 norm

Erorrs come from

• $T \ne \hat{T}$
  • Sampling Error

• $\hat{Q}_{k+1} \ne \hat{T}\hat{Q}_k$
  • Approximation Error

Sampling Error:

Note:

• $|\hat{r}(s,a) - r(s,a)|$
  • Estimation error of continuous random variable, use Hoeffding’s Inequality!
  • $\le 2 R_{max} \sqrt{\frac{\log (\delta^{-1})}{2N}}$

• $|\mathbb{E}{\hat{P}}[\max{a'}Q(s',a')]-\mathbb{E}{P}[\max{a'}Q(s',a')]|$
  • $= \sum_{s’} (\hat{P}(s’|s,a) - P(s’|s,a)) \max_{a’} Q(s’,a’)$
  • $\le \sum_{s’} |\hat{P}(s’|s,a) - P(s’|s,a)| \max_{s’,a’} Q(s’,a’)$
    • $= ||\hat{P}(\cdot|s,a) - P(\cdot|s,a)||_1 ||Q||_\infin$
  • $\le c||Q||_\infin \sqrt{\frac{\log(\delta^{-1})}{N}}$

So

And

Approximation Error:

Assume error: $||\hat{Q}_{k+1} - T\hat{Q}_k||_\infin||_\infin \le \epsilon_k$

This is a strong assumption!

Putting it together:

Note:

From previous proofs, $\text{Sampling Error}, \text{Approx Error} \in O((1-\gamma)^{-1})$

More advanced results can be derived with $p$-norms under some distribution