We can study the sample complexity of ♟️ Reinforcement Learning algorithms, specifically for a simplified setting that ignores exploration (which would introduce another layer of design and complexity): assume for every , we can sample times.

As a representative example, we'll study model-based RL, which will build a model and estimate value for policy . We'll answer a series of questions:

1. How accurate is the value estimate? With some conditions,

2. How accurate is the value estimate for an optimal policy? With some conditions,

3. How good is the resulting policy? With some conditions,

Concentration Inequalities#

First, we need a bound on how close a learned function is to the true function, in terms of the number of samples. We'll use Hoeffding's inequality, which states that for a sequence of samples (between 0 and 1) with mean , the estimated mean is off by more than error with probability at most ,

If we want this probability to be , rearranging shows that the error scales with .

Note that this inequality is for counts, and for probabilities there is a similar bound . Applying this to our case, we can bound the error on the estimated model ,

with probability , for a constant (that we can simplify and ignore).

Model-Based RL#

Next, we'll relate the error in to the error in . Borrowing the linear algebra from 🍥 Convergence, we have

since and defining . Then, solving for gives

Simulation Lemma#

With the equation above and some algebraic manipulation, we arrive at the simulation lemma, which relates the value error as

Intuitively, this is saying that the value error is itself like a Q-function (with the gamma inverse part like above) on reward . Thus, error is high for large mistakes in the model at high value states.

We also need another lemma that describes the impact of the above evaluation operator on the reward's norm. For any reward , triangle inequality gives us

This says that the largest possible value is the largest reward multiplied with the horizon .

Conclusion#

Putting everything together, we substitute from the simulation lemma into the of the second lemma, and after some manipulation and the concentration inequality, we have the error bound

for all 3 questions at the top. Note this assumes the largest reward is .

The main takeaway is that error scales with samples as , and grows quadratically with horizon as (intuitively since each backup accumulates error).

Model-Free RL#

We can extend this analysis to model-free RL, specifically 💎 Value Iteration > Fitted Q-Iteration. The algorithm can be expressed as

where is the approximate Bellman operator that uses samples to estimate . The is simply the fitting of the function approximator, which usually is a projection on the 2-norm, but for simplicity we'll study the infinity-norm.

Like above, our key question is how good our estimated Q-function can get,

as a result of error from and the projection.

Sampling Error#

The sampling error comes from . Comparing the difference in using and for the backup, we can leverage Hoeffding's inequality and XX to arrive at

where the two terms come from error in the sample estimate of reward and transitions , respectively.

Approximation Error#

The approximation error comes from . We'll assume

Ignoring the sampling error for now (so using ), we can derive the value error as

This is a recursive relationship from to , and unrolling it through time gives us

This essentially says that error compounds over backups every time we iterate, since we're using the approximated Q-function as the target.

Conclusion#

Putting these two errors together, we essentially see that the sampling error goes into the recursive relation of the approximation error, and thus in total grows with the quadratic horizon .