AI & Math Blog
Reinforcement Learning: Sample Complexity

Introduction

This page summarizes some recent mathematical advances on sample complexity in reinforcement learning (RL).
Imagine you are teaching a robot how to play chess. You want it to learn the best moves, with a limited number of games to train it with. Sample complexity is all about how efficiently your robot can learn from those limited games. It measures how many games, or interactions, the robot needs to play before it can figure out the best moves. A lower sample complexity means it learns faster, even with limited training data. In real-world scenarios like self-driving cars, collecting data for training can be very expensive and time-consuming. This is where sample complexity becomes crucial. Algorithms with low sample complexity can learn effectively even with limited real-world driving data. So, how can we design algorithms that learn quickly and efficiently, even with limited data? This is where the study of sample complexity comes in.

The standard framework for RL is the Markov decision process (MDP). For the sake of generality, we consider the infinite horizon discounted MDP defined by $\mathcal{M}=(\mathcal{S,A,P},r,\gamma )$ where $\mathcal{S,A}$ are respectively the state space and the action space, which might be infinite, $r : \mathcal{S\times A} \rightarrow [0,1]$ is the reward function, i.e., $r(s,a)$ is the immediate reward upon choosing the action $a \in \mathcal{A}$ while in the state $s \in \mathcal{S}$, and $\gamma \in (0,1)$ is the discount factor.
The probability transition kernel is defined as $\mathcal{P}: \mathcal{S \times A} \rightarrow \Delta(S)$, where $\mathcal{P}(s^{'}|s,a)$ is the probability of transiting from state $s$ to state $s^{'}$ when $a$ is selected; $\Delta(S)$ is the probability simplex over $\mathcal{S}$. In the generative case, the probability transition kernel $\mathcal{P}$ is empirically estimated from the data.
We consider here the standard tabular case: the cardinalities $|\mathcal{S}|$ and $|\mathcal{A}|$ are finite.

A deterministic policy $\pi$ is a mapping $\pi: \mathcal{S}\rightarrow \mathcal{A}$. The objective of the agent is to find the optimal policy $\pi^\star$ maximizing the value function $V^\pi(s)$ . For the infinite horizon discounted MDP, $V^\pi(s)$ is the expected discounted total reward starting from the initial state $s^0=s$ , i.e., \begin{eqnarray*} \pi^\star &:= &\arg \max_\pi V^\pi(s),\\ V^\pi(s)& := &E \Big[ \sum_{t=0}^\infty \gamma^t r(s^t, a^t)\big | s^0 = s \Big ]. \end{eqnarray*} The corresponding action value function $Q^\pi: \mathcal{S\times A} \rightarrow \mathbb{R}$ of a policy $\pi$ is defined as $$ Q^\pi(s,a) := E \Big [ \sum_{t=0}^\infty \gamma^t r(s^t, a^t) \big | (s^0, a^0)=(s, a) \Big ], $$ $\forall (s,a) \in \mathcal{S \times A}$. There exists an optimal policy $\pi^\star$ that simultaneoulsy maximizes $V^\pi(s) \; \forall s \in \mathcal{S}$, and $Q^\pi(s,a) \; \forall (s,a) \in \mathcal {S \times A}$. Denote the optimal value function $V^\star := V^{\pi^\star}$, and the optimal action value function $Q^\star := Q^{\pi^\star}$.

Given a few data samples, the aim of policy learning is to find/identify a policy that maximizes the expected discounted reward. Formally, let $\varepsilon$ be the target accuracy level, an $\varepsilon$-accurate policy $\pi_\text{est}$ is defined as \begin{eqnarray*} V^{\pi_{\text{est}}}(s) &\geqslant& V^\star(s) -\varepsilon,\\ Q^{\pi_{\text{est}}}(s,a) &\geqslant& Q^\star(s,a) -\varepsilon, \end{eqnarray*} $\forall (s,a) \in \mathcal{S\times A}$. The sample complexity of a RL algorithm is the minimum number of calls to a sampling model required for the algorithm to learn a policy that is within a specified target accuracy level, $\varepsilon$ of the optimal policy, with high probability. Formally, the sample complexity $m(\varepsilon, \delta)$ is the smallest number of samples such that, for any $\delta \in (0,1)$, the learned policy $ \pi$ is an $\varepsilon$-accurate policy, i.e., \begin{eqnarray*} V^{\pi}(s) &\geqslant& V^\star(s) -\varepsilon,\\ Q^{\pi}(s,a) &\geqslant& Q^\star(s,a) -\varepsilon, \end{eqnarray*} with probability at least $1 - \delta$. In RL, there is a trade-off between sample complexity and statistical accuracy: exploring more information to improve statistical accuracy, versus exploiting known actions to maximize reward, which reduces sample complexity.
The two common frameworks for analyzing sample complexity are:
  1. On the one hand, the PAC bounds which allow to determine the number of samples needed to guarantee that the algorithm learns a policy with a small accuracy error $\varepsilon$, compared to the optimal policy, see e.g., Azar et al. (2013),
  2. On the other hand, the regret bounds measure the cumulative loss incurred before reaching the optimal policy. They quantify how much reward we miss out on during the learning process, see e.g., Azar et al. (2017).

Recent Advances

Lan (2023) studied the sample complexity of two stochastic versions of a new policy mirror descent (PMD) for RL problems with either convex or strictly convex regularizers. Li, Shi et al. (2024) consider both frameworks of discounted infinite-horizon and finite-horizon MDPs, and design an offline model-based RL algorithm achieving the minimax-optimal sample complexity without burn-in costs. Zhang et al. (2023) study the sample complexity of a model-based multi-agent RL (MARL) in zero- sum discounted Markov games, when a generative model is available. Sample complexity can be improved by hierarchical reinforcement learning (HRL) models, see e.g., Robert et al. ( 2023), Brunskill and Li (2014). The Goal-Conditioned HRL approach allows to achieve lower sample complexity while maintaining efficiency.
Li, Wei et al. (2024) consider the framework of the infinite horizon discounted MDP with a generative model. Denote by $\mathcal{M} =(\mathcal{S,A},\widehat{\mathcal{P}}, r,\gamma) $ the empirical MDP, where the empirical kernel $\widehat{\mathcal{P}}$ is estimated from a collection of $N$ i.i.d samples $s_{s,a}^i \sim \mathcal{P}(.|s,a)$: $$ \forall s^{'} \in \mathcal{S}, \quad \widehat{\mathcal{P}}(s^{'}|s,a):= \frac{1}{N}\sum_{i=1}^N\mathbf{1}\{s_{s,a}^i = s^{'} \}. $$ Two algorithms are studied:
  1. The first algorithm, i.e., the perturbed model-based planning (PBMP), is defined by adding a random term $\zeta(s,a)$, with $(s,a) \in \mathcal{S}\times \mathcal{A}$, to the reward function, i.e., \begin{equation*} r_p(s,a) =r(s,a)+ \zeta(s,a), \quad \zeta(s,a) \sim \text{i.i.d } U(0,\xi) , \end{equation*} where $U(0, \xi)$ denotes the uniform distribution on the interval $(0,\xi)$, $\xi$ being the perturbation size. The optimal policy $\hat{\pi}^\star_p$ of the perturbed empirical MDP $\widehat{\mathcal{M}}_p =(\mathcal{S,A},\widehat{\mathcal{P}},r_p,\gamma)$ is defined as \begin{equation*} \label{e:PBMP} \hat{\pi}^\star_p := \arg \max_\pi \widehat{V}^\pi_p. \end{equation*}
  2. The second algorithm consists in selecting the approximate optimal action, for the empirical MDP $\mathcal{M}$ as follows: $$ \hat{\pi}_\varsigma(s) := \min \Big \{ a \in \mathcal{A} : \widehat{Q}^\star(s,a) > \widehat{V}^\star(s) - \varsigma \Big \}, $$ $\forall s \in \mathcal{S}$, where $\varsigma \sim U(0,\xi)$.
The sample complexity of these two algorithms is equal to $ \frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^3 \varepsilon^2} $ as in Agarwal et al. (2020), Sidford et al. (2018), and Azar et al. (2013). However, for both algorithms, the minimum sample size for achieving the minimax sample complexity is $ N \geqslant \widetilde{\Omega}\left(\frac{|\mathcal{S}||\mathcal{A}|}{1-\gamma}\right)$. This improves upon the previous results $N\geqslant \widetilde{\Omega}\left(\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^2}\right)$ obtained by Agarwal et al. (2020), and $N\geqslant \widetilde{\Omega}\left(\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^3}\right)$ by Sidford et al. (2018).
Define $\mathcal{X} := \Big (\mathcal{|S|,|A|},\frac{1}{1-\gamma},\frac{1}{\varepsilon} \Big )$. The standard notation $f(\mathcal{X})= \mathcal{O}(g(\mathcal{X}))$ means that $\exists\, C >0$ such that $f\, \leqslant \, Cg$, $f(\mathcal{X})= \Omega(g(\mathcal{X})$ means that $g(\mathcal{X})= \mathcal{O}(f(\mathcal{X}))$, while $f(\mathcal{X})= \widetilde{\Omega}(g(\mathcal{X}))$ is identical as the previous definition of $\Omega (\cdot)$ disregarding the logarithmic factors in $\mathcal{X}$.

Federated Reinforcement Learning

Federated Reinforcement Learning (FRL) presents unique challenges due to its decentralized nature. Two key complexities significantly impact FRL's performance and scalability: sample complexity and communication complexity. Sample complexity refers to the amount of data each agent needs to learn an effective policy, while communication complexity quantifies the information exchanged between agents and the central server during training, with possibly limited communication resources.
Efficient FRL algorithms strive to minimize both complexities, that are intertwined; high sample complexity may necessitate more frequent communication, increasing overall communication costs, whilst limited communication bandwidth can restrict the amount of data agents can share, potentially increasing sample complexity.
Woo et al. (2025) study the sample complexity of federated $Q$-learning under both the synchronous and asynchronous case, in the infinite horizon tabular MDP. In the general asynchronous case, each agent $k \in [K]=\{1,\ldots,K\}$ samples local trajectories $\big \{ s_t^k, a_t^k, r_t^k \big \}_{t=0}^\infty $ from the same MDP $\mathcal{M}$ using different stationary local policies $\{\pi^k_b\}_{k\in[K]}$:
$$ a_t^k \sim\pi_b^k(\cdot|s_t^k), \quad r_t^k = r(s_t^k,a_t^k),\quad s_{t+1}^k \sim P(\cdot|s_t^k, a_t^k), \quad \forall t \geqslant 0. $$
$ a_t^k \sim\pi_b^k(\cdot|s_t^k)$, $r_t^k = r(s_t^k,a_t^k)$, $s_{t+1}^k \sim P(\cdot|s_t^k, a_t^k)$, $\forall t \geqslant 0. $
The Federated Asynchronous $Q$-learning algorithm is defined by the update equation:
$$ \label{e:fedasyncup} Q^k_{t-\frac{1}{2}}(s,a) := \left \{ \begin{array}{ll} (1-\eta) Q^k_{t-1}(s,a) +\eta \big (r_{t-1}^k +\gamma V^k_{t-1}(s_t^k) \big ) & \text{if}\; (s,a) = (s^k_ {t-1},a^k_{t-1}) \\ Q^k_{t-1}(s,a) & \text{otherwise} \end{array} \right ., $$
$ \label{e:fedasyncup_s} Q^k_{t-\frac{1}{2}}(s,a) :=
$ $$ \left \{ \begin{array}{l} (1-\eta) Q^k_{t-1}(s,a) +\eta \big (r_{t-1}^k +\gamma V^k_{t-1}(s_t^k) \big )\\ \qquad \text{if}\; (s,a) = (s^k_ {t-1},a^k_{t-1}) \\ Q^k_{t-1}(s,a) \quad \text{otherwise} \end{array} \right ., $$
where $\eta$ is the learning rate, and the periodic averaging function at the end of each $t$-th iteration by a central server:
$$ \label{e:fedasync} \forall (s,a) \in \mathcal{S\times A} \quad Q^k_t(s,a) := \left \{ \begin{array}{ll} \sum_{k=1}^K \alpha_t^k(s,a)Q^k_{t-\frac{1}{2}}(s,a) & \text{if}\; t\equiv 0 \;(\!\!\!\!\!\mod \tau)\\ Q^k_{t-\frac{1}{2}}(s,a) & \text{otherwise} \end{array} \right ., $$
$\label{e:fedasync_s} \forall (s,a) \in \mathcal{S\times A} \quad Q^k_t(s,a) :=
$ $$ \left \{ \begin{array}{ll} \sum_{k=1}^K \alpha_t^k(s,a)Q^k_{t-\frac{1}{2}}(s,a) & \text{if}\; t\equiv 0 \;(\!\!\!\!\!\mod \tau)\\ Q^k_{t-\frac{1}{2}}(s,a) & \text{otherwise} \end{array} \right ., $$
where $\alpha_t^k(s,a)$ are weights assigned to agent $k$ so that $\sum_{k=1}^K \alpha_t^k(s,a) = 1$. Define the final estimate $Q_T = \frac{1}{K}\sum_k Q_T^k$, where $T$ is the total number of iterations. The performance guarantees depend, among other things, on salient parameters characterizing the Markov chain induced by $\pi_b^k$. In particular, they depend on the stationary state-action distribution $\mu_b^k$ of the Markov chain, which is assumed to be uniformly ergodic over $\mathcal{S \times A}$; see Li et al. (2022). The sample complexity depends on the choice for the weights $\alpha_t^k(s,a)$. For the importance averaging scheme defined as: $$ \label{e:impavg} \alpha_t^k(s,a) := \frac{(1-\eta)^{-N_{t-\tau,t}^k(s,a)}} {\sum_{k^{'}=1}^K (1-\eta)^{-N_{t-\tau,t}^{k^{'}}(s,a)}}, $$ where $N_{t-\tau,t}^k(s,a)$ is the number of iterations $ t-\tau \leqslant i \lt t$ when agent $k$ visits $(s,a)$. The sample complexity, i.e., the number of samples required for achieving $\|Q_T-Q^* \|_\infty \leqslant \varepsilon$ for the algorithm based on the update and averaging functions, and the importance averaging scheme is: $$ \widetilde{\mathcal{O}} \left ( \frac{1}{K \mu_\text{avg}(1-\gamma)^5 \varepsilon^2 } \right), $$ where $\mu_\text{avg} := \min_{(s,a)\in \mathcal{S \times A}} \frac{1}{K}\sum_{k=1}^K \mu_b^k(s,a)$, i.e., the minimum of the average state-action distribution for all agents. As mentioned above, $\widetilde{\mathcal{O}}$ is identical as the standard definition of $\mathcal{O}$ disregarding the logarithmic factors. The sample complexity does not depend on the heterogeneity of $\mu_b^k(s,a)$ across agents. Lastly, the communication complexity of this algorithm is $\widetilde{\mathcal{O}}\left ( \frac{K}{\mu_\text{avg} (1-\gamma)} \right)$.

References

  1. Abernethy, J., Agarwal, A., Marinov, T.V. and Warmuth, M.K., 2024. A mechanism for sample-efficient in-context learning for sparse retrieval tasks. Proceedings of Machine Learning Research, PMLR 237, 3-46. MR4740478
  2. Agarwal, A., Kakade, S. and Yang, L.F., 2020. Model-based reinforcement learning with a generative model is minimax optimal. Proceedings of Thirty Third Conference on Learning Theory, PMLR 125, 67-83.
  3. Agarwal, A., Kakade, S., Krishnamurthy, A. and Sun, W., 2020. Flambe: Structural complexity and representation learning of low rank MDPs. Advances in neural information processing systems, 33, 20095-20107.
  4. Agarwal, A., Kakade, S.M., Lee, J.D. and Mahajan, G., 2021. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98), 1-76. MR4279749
  5. Azar, M.G., Osband, I. and Munos, R., 2017. Minimax regret bounds for reinforcement learning. Proceedings of the 34th International Conference on Machine Learning, PMLR 70, 263-272.
  6. Azar, M.G., Munos, R. and Kappen, H.J., 2013. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model. Machine Learning, 91, 325-349. MR3064431
  7. Brunskill, E. and Li, L., 2014. PAC-inspired option discovery in lifelong reinforcement learning. Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):316-324.
  8. Ehrenfeucht, A., Haussler, D., Kearns, M. and Valiant, L., 1989. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3), 247-261. MR1016683
  9. Kairouz, P. et al 2021. Advances and open problems in federated learning. Foundations and trends® in machine learning, 14(1–2), 1-210.
  10. Kakade, S.M., 2003. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom).
  11. Kearns, M. and Singh, S., 2002. Near-optimal reinforcement learning in polynomial time. Machine learning, 49, 209-232.
  12. Kearns, M. and Singh, S., 1998. Finite-sample convergence rates for $Q$-learning and indirect algorithms. Advances in neural information processing systems, 11.
  13. Lan, G., 2023. Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes.Mathematical Programming, 198, no.1, Ser. A, 1059-1106. MR4550970
  14. Li, G., Cai, C., Chen, Y., Wei, Y. and Chi, Y., 2024. Is $Q$-learning minimax optimal? A tight sample complexity analysis. Operations Research, 72(1), 222-236. MR4705835
  15. Li, G., Wei, Y., Chi, Y. and Chen, Y., 2024. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Operation Research, 72(1), 203–221. MR4705834
  16. Li, G., Shi, L., Chen, Y., Chi, Y. and Wei, Y., 2024. Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, 52(1), pp233-260. MR4718414
  17. Li, G., Wei, Y., Chi, Y., Gu, Y. and Chen, Y., 2022. Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. IEEE Transactions on Information Theory, 68(1), 448-473. MR4395423
  18. Li, T., Lan, G. and Pananjady, A., 2023. Accelerated and instance-optimal policy evaluation with linear function approximation. SIAM Journal on Mathematics of Data Science, 5(1), pp174-200. MR4562584
  19. McMahan, B., Moore, E., Ramage, D., Hampson, S. and y Arcas, B.A., 2017. Communication-efficient learning of deep networks from decentralized data. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:1273-1282.
  20. Pananjady, A. and Wainwright, M.J., 2021. Instance-dependent $\ell_\infty $-bounds for policy evaluation in tabular reinforcement learning. IEEE Transactions on Information Theory,67(1) 566–585. MR4231973
  21. Robert, A., Pike-Burke, C. and Faisal, A.A., 2023. Sample complexity of goal-conditioned hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 36, 62696-62712
  22. Sidford, A., Wang, M., Wu, X., Yang, L. and Ye, Y., 2018. Near-optimal time and sample complexities for solving Markov decision processes with a generative model. Advances in Neural Information Processing Systems, 31.
  23. Strehl, A.L. and Littman, M.L., 2008. An analysis of model-based interval estimation for Markov decision processes. Journal of Computer and System Sciences, 74(8), pp1309-1331. MR2460287
  24. Sutton, R.S. and Barto, A.G., 2018. Reinforcement learning: an introduction. Second edition Adapt. Comput. Mach. Learn. MIT Press, Cambridge, MA. MR3889951
  25. Szepesvàri, C., 2022. Algorithms for reinforcement learning, reprint of the 2010 original, Synthesis Lectures on Artificial Intelligence and Machine Learning, 9, Springer, Cham, MR4647095
  26. Teyssière, G., 2023. Review of "Lan, G., 2023. Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes". Mathematical Reviews, American Mathematical Society.
  27. Teyssière, G., 2025. Review of "Li, G., Wei, Y., Chi, Y. and Chen, Y., 2024. Breaking the sample size barrier in model-based reinforcement learning with a generative model". Mathematical Reviews, American Mathematical Society.
  28. Teyssière, G., 2025. Review of "Woo, J., Joshi, G. and Chi, Y., 2025. The blessing of heterogeneity in federated $Q$-learning: Linear speedup and beyond.". Mathematical Reviews, American Mathematical Society.
  29. Valiant, L.G., 1984. A theory of the learnable. Communications of the ACM, 27 (11), 1134-1142.
  30. Wainwright, M.J., 2019. Stochastic approximation with cone-contractive operators: Sharp $\ell_\infty$-bounds for $Q$-learning. arXiv preprint arXiv:1905.06265.
  31. Wang, M., 2020. Randomized linear programming solves the markov decision problem in nearly linear (sometimes sublinear) time. Mathematics of Operations Research, 45(2), 517-546. MR4100273
  32. Woo, J., Joshi, G. and Chi, Y., 2025. The blessing of heterogeneity in federated $Q$-learning: Linear speedup and beyond. Journal of Machine Learning Research, 26(26), 1-85. MR4873577
  33. Zhang, K., Kakade, S.M., Başar, T. and Yang, L.F., 2023. Model-based multi-agent RL in zero-sum markov games with near-optimal sample complexity. Journal of Machine Learning Research, 24(175), 1-53. MR4633564
  34. Zhang, Z., Chen, Y., Lee, J. and Du, S.S., 2025. Settling the Sample Complexity of Online Reinforcement Learning. Journal of the ACM, 72(3), 1-63. MR4926208
Updated Janvier 2026.