Theoretical RL: Sample, Regret, Proof

Why Does This Exist?

An agent can top a benchmark table and still fail you. Benchmarks report what happened on a fixed set of runs. They say nothing about the next environment, the next seed, or how many bad episodes you will pay for before the policy turns good. If you are putting an agent on hardware, on traffic, or on money, "it learned eventually in our runs" is not a plan. You need a counted cost, stated before training starts.

That is the job of theoretical RL. It proves statements of the form: under assumptions X, algorithm Y acts near-optimally after at most N steps, with high probability. The number N is the price tag. The assumptions are the fine print.

This page is the umbrella. It teaches the three kinds of price tags (sample complexity, regret, PAC-MDP certificates), the two settings they apply to (small finite tables versus function approximation), and the one design idea behind most efficient algorithms (optimism). Each guarantee type gets its own deep page later; here you get them described and compared, not fully derived.

The one idea you need first.

A Markov decision process is the tuple of states, actions, rewards, and transition probabilities the agent lives in, and value iteration computes optimal values when the model is known. Theory starts where that comfort ends: the model is unknown, so the agent must learn it by acting, and acting badly while learning has a cost. How the agent balances that cost is the exploration problem, and the update rule most analyses study is temporal-difference learning.

Think of It Like This

How It Actually Works

Theory speaks in three currencies. They answer different questions, and mixing them up is the source of most confusion.

Sample complexity asks: how many steps until the agent behaves near-optimally? Formally, the number of timesteps after which the agent's policy $\pi$ (its rule for picking actions) satisfies $V^{\pi} \geq V^{\star} - \eta$: its long-term return sits within $\eta$, your accuracy demand, of the best achievable return $V^{\star}$. This is the price tag most practitioners want.

Regret asks: how much reward did the agent leave on the table while learning? Cumulative regret after $T$ steps is $\sum_{t=1}^{T} (V^{\star} - V^{\pi_t})$: the gap between the best return and what the agent actually banked, added up over every step. An algorithm whose regret grows slower than $T$ (sublinear regret, for example proportional to $\sqrt{T}$) gets closer to optimal per step as time passes. Sample complexity counts steps to good behavior; regret prices every bad step on the way there.

PAC-MDP (Probably Approximately Correct in MDPs) is the certificate format: with probability at least $1 - \delta$ (your confidence demand; $\delta = 0.05$ means 95 percent confidence), the algorithm is $\eta$-optimal on all but a bounded number of steps. It wraps a sample-complexity count inside an explicit confidence statement. The PAC-MDP framework page carries the full definition.

Why do tabular and approximation results look so different?

In the tabular regime, every state-action pair $(s, a)$ has its own counter and its own stored value. With $S$ states and $A$ actions there are $S \times A$ pairs to learn, and the bounds scale with that product: more pairs, more samples, linearly. Counting visits works because each pair is visited again and again, so averages concentrate around true values by standard statistics.

In the function-approximation regime, states are too many to count (pixels, sensor streams), so the agent generalizes with a model such as a linear predictor or a neural network. Generalization breaks the counting argument: visiting one state tells you something about others, but only if the function class is structured the right way. Positive results here always carry a structural assumption (linear dynamics, bounded Bellman rank, bounded eluder dimension), and the bound scales with the structure's complexity instead of $S \times A$. With no structural assumption, there is no finite guarantee at all. That is a theorem too, not a gap in the literature.

What is optimism, and why does it keep working?

Most sample-efficient algorithms share one trick: optimism in the face of uncertainty. When the agent is unsure about an action's value, it acts as if the action is as good as plausibly possible, tries it, and corrects the estimate with what it observes. An action is either good (profit) or disappointing (information that shrinks the uncertainty), so the agent cannot stay wrong for long.

Concretely, algorithms add an exploration bonus to uncertain pairs, proportional to something like $1/\sqrt{n(s,a)}$ where $n(s,a)$ is the visit count: a large bonus for strangers, near zero for old friends. The bonus decays exactly as fast as the statistical uncertainty does, which is why total regret stays bounded instead of growing forever. This is the principled cousin of the hand-tuned trial and error on the exploration page: same dilemma, but the bonus is sized from the math rather than tuned by hand.

Worked mini-calculation: what does epsilon-greedy really cost?

Take a tiny tabular task: $S = 5$ states, $A = 2$ actions, so $S \times A = 10$ pairs to learn. The agent runs epsilon-greedy (a random action with probability $\epsilon = 0.1$, its current best guess otherwise) and you demand each pair's value accurate within $\eta = 0.1$ at confidence $1 - \delta = 0.95$.

Step 1, samples per pair. A standard concentration bound says $n \geq \ln(2/\delta) / (2\eta^2)$ samples pin one value down to $\pm\eta$. Plug in: $\ln(2/0.05) = \ln(40) \approx 3.6889$, and $2\eta^2 = 0.02$. So $n \geq 3.6889 / 0.02 \approx 184.44$, rounded up to 185 samples per pair.

Step 2, all pairs. Covering 10 pairs needs $185 \times 10 =$ 1,850 well-spread samples.

Step 3, the epsilon tax. Only a fraction $\epsilon = 0.1$ of steps are random, and only random steps spread evenly, so total interaction steps come to $1{,}850 / 0.1 =$ 18,500 steps.

Read the scaling off the arithmetic: cost grows linearly with the pair count, quadratically with $1/\eta$ (halve the error tolerance and the per-pair count jumps from 185 to about 18,445), logarithmically with $1/\delta$ (confidence is cheap), and inversely with $\epsilon$ (timid exploration multiplies the total). That single jump from 185 to 18,445 explains why theory papers obsess over the accuracy parameter.

Code

A short script that prices the worked example, so you can reprice it for your own numbers.

1import math2
3
4def hoeffding_samples(accuracy: float, delta: float) -> int:5    """Samples needed to pin one action value within accuracy at confidence 1 - delta."""6    return math.ceil(math.log(2.0 / delta) / (2.0 * accuracy**2))7
8
9def total_steps(num_pairs: int, accuracy: float, delta: float, epsilon: float) -> int:10    """Total interaction steps when only an epsilon fraction spreads evenly."""11    return math.ceil(hoeffding_samples(accuracy, delta) * num_pairs / epsilon)12
13
14print(hoeffding_samples(0.1, 0.05))  # -> 18515print(total_steps(10, 0.1, 0.05, 0.1))  # -> 1850016print(hoeffding_samples(0.01, 0.05))  # -> 18445

The first two lines replay the hand arithmetic exactly, and the third shows the accuracy tax: demanding $\eta = 0.01$ instead of $0.1$ multiplies the per-pair bill by one hundred.

Watch Out For

The Quick Version

• Theoretical RL prices learning: sample complexity counts steps to near-optimal behavior, regret totals the reward lost along the way, and PAC-MDP wraps the count in an explicit confidence statement.
• Tabular bounds scale with the state-action pair count because each pair is counted separately; approximation bounds scale with structural complexity and vanish entirely without a structural assumption.
• Optimism in the face of uncertainty, trying uncertain actions as if they were good, is the shared trick behind most efficient algorithms, with bonuses sized from statistics rather than tuned by hand.
• The scaling is concrete: 10 pairs at accuracy 0.1 and 95 percent confidence need 185 samples each, 1,850 spread samples, and 18,500 epsilon-greedy steps, while accuracy 0.01 needs 18,445 per pair.
• A guarantee covers only its assumptions: instantiate the bound with your numbers before budgeting, and never cite a tabular certificate for an approximated agent.

What to Read Next

• Markov Decision Processes
• Exploration vs. Exploitation
• Temporal Difference Learning
• Value Iteration in RL