sample complexity

Sample complexity asks a budgeting question: how many interactions with the environment — transitions, episodes, or steps — does a learner need before it can output a near-optimal policy? It is the RL cousin of "how many examples does supervised learning need," but harder, because in RL the data you collect depends on the policy you are running, and a poor early policy can starve you of information about exactly the states that matter most.

Formally we fix an accuracy ε and a confidence 1−δ and ask for the smallest number of samples N(ε,δ) such that, with probability at least 1−δ, the returned policy is within ε of optimal. Bounds typically scale with the number of states S, actions A, the effective horizon 1/(1−γ), and 1/ε. The horizon dependence is usually the dominant and most delicate term; shaving even one factor of 1/(1−γ) is a celebrated theoretical result.

Sample complexity is worst-case over a class of MDPs, so it can look pessimistic next to what works in practice. Its real value is comparative: it tells you which structural assumptions — a generative model, linear features, low Bellman rank — actually buy you cheaper learning.