Why a working agent is not the end of the story
An empirical result tells you that some run of some algorithm reached a good policy on one task. Theory asks the harder questions: will it work on every problem in a class, how much data does it need, and is there a fundamentally better algorithm waiting to be found? Once you have studied what RL is and the MDP formalism, theory is what turns a pile of tricks into a science with guarantees and limits.
Diagram of an agent taking an action, the environment returning a reward and next state, repeating.
Three currencies: sample complexity, regret, PAC
Theory measures cost in a few standard currencies. Sample complexity counts how many environment interactions you need before the learned policy is provably near-optimal. Regret sums, over an entire run, how much reward you lost relative to acting optimally from the start — it charges you for every mistake along the way, not just the final answer. PAC-RL (Probably Approximately Correct) demands a policy within ε of optimal with probability at least 1−δ, and bounds the samples needed as a function of ε and δ.
- Sample complexity asks: how many samples until 'good enough'? (a budget question)
- Regret asks: how much did I pay while learning? (an online, cumulative question)
- PAC asks: with what confidence, and to what accuracy, can I certify the result? (a guarantee question)
Lower bounds: what no algorithm can beat
An upper bound says 'this algorithm is at least this good.' A minimax lower bound says the opposite and far stronger thing: no algorithm can do better than this on the worst case in the class. When an algorithm's upper bound matches the lower bound (up to constants and log factors), we call it minimax-optimal — the problem is, in a precise sense, solved. Lower bounds are built by constructing pairs of MDPs that are statistically hard to tell apart, so any learner must gamble.
A minimax regret lower bound: no algorithm can avoid paying on the order of the square root of HSAT in the worst case.
The gap between the best known upper bound and the best known lower bound is the frontier of the field. Closing it — by finding a smarter algorithm or a harder hard instance — is what theory papers fight over.
The exploration tax
In supervised learning your data is handed to you. In RL you must collect it by acting, so a learner that never tries unfamiliar actions can stay forever ignorant of a better policy. The exploration–regret tradeoff is the formal version of the explore/exploit dilemma: every exploratory step that turns out badly is charged to your regret, yet refusing to explore caps how good you can ever get. Theory quantifies exactly how much exploration the optimal tradeoff requires.
Interactive gridworld where a Q-learning agent must explore cells to discover higher-reward paths.
Choosing the objective changes the theory
Before any bound, you must fix the objective. The discounted criterion weights near-term reward more and has an effective horizon of roughly 1/(1−γ), which shows up everywhere in discounted bounds. The average-reward criterion instead measures long-run reward per step and is the natural objective for genuinely continuing tasks with no discounting. Average-reward theory is subtler — it leans on the mixing time or diameter of the MDP rather than on 1/(1−γ).
The discounted return and its effective horizon of about 1/(1-gamma) - the objective whose choice reshapes every later bound.
Keep this map in mind for the rest of the track. Next we prove why the classic dynamic-programming and tabular Q-learning methods converge at all — the bedrock that the harder results build on.