Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning

References

• [1] Agarwal A, Kakade S, Yang LF (2020) Model-based reinforcement learning with a generative model is minimax optimal. Abernethy J, Agarwal S, eds. Proc. 33rd Conf. Learn. Theory, PMLR, vol. 125 (PMLR, New York), 67–83.Google Scholar
• [2] Auer P, Ortner R (2006) Logarithmic online regret bounds for undiscounted reinforcement learning. Adv. Neural Inform. Processing Systems 19:49–56.Google Scholar
• [3] Ayoub A, Jia Z, Szepesvari C, Wang M, Yang L (2020) Model-based reinforcement learning with value-targeted regression. Daumé H III, Singh A, eds. Proc. 37th Internat. Conf. Machine Learn., PMLR, vol. 119 (PMLR, New York), 463–474.Google Scholar
• [4] Bai Y, Xie T, Jiang N, Wang Y-X (2019) Provably efficient q-learning with low switching cost. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 8002–8011.Google Scholar
• [5] Bertsekas DP (2017) Dynamic Programming and Optimal Control, 4th ed. (Athena Scientific, Belmont, MA).Google Scholar
• [6] Brafman RI, Tennenholtz M (2002) R-max–A general polynomial time algorithm for near-optimal reinforcement learning. J. Machine Learn. Res. 3(Oct):213–231.Google Scholar
• [7] Chen F, Mei S, Bai Y (2025) Unified algorithms for RL with decision-estimation coefficients: PAC, reward-free, preference-based learning, and beyond. Ann. Statist. 53(1):426–456.Google Scholar
• [8] Chen X, Hu J, Yang LF, Wang L (2021) Near-optimal reward-free exploration for linear mixture MDPs with plug-in solver. Preprint, submitted October 7, https://arxiv.org/abs/211003244.Google Scholar
• [9] Chen J, Modi A, Krishnamurthy A, Jiang N, Agarwal A (2022) On the statistical efficiency of reward-free exploration in non-linear RL. Adv. Neural Inform. Process. Systems 35:20960–20973.Crossref, Google Scholar
• [10] Chen Y, Chi Y, Fan J, Li G, Wei Y, Yan Y (2026) Statistical foundations of reinforcement learning: A nonasymptotic perspective.Google Scholar
• [11] Chi Y, Chen Y, Wei Y (2025) Statistical and algorithmic foundations of reinforcement learning. Denton BT, Tanik Argon N, Xie Y, eds. Advances in Analytics and Operations Research: Improving Decisions to Secure the Future, INFORMS TutORials in Operations Research (INFORMS, Catonsville, MD), 104–144.Link, Google Scholar
• [12] Cui Q, Du SS (2022) Provably efficient offline multi-agent reinforcement learning via strategy-wise bonus. Adv. Neural Inform. Processing Systems 35:11739–11751.Google Scholar
• [13] Cui Q, Du SS (2022) When is offline two-player zero-sum Markov game solvable? Adv. Neural Inform. Processing Systems 35:25779–25791.Google Scholar
• [14] Domingues OD, Ménard P, Kaufmann E, Valko M (2021) Episodic reinforcement learning in finite MDPs: Minimax lower bounds revisited. Feldman V, Ligett K, Sabato S, eds. Proc. 32nd Internat. Conf. Algorithmic Learn. Theory, PMLR, vol. 132 (PMLR, New York), 578–598.Google Scholar
• [15] Dong K, Wang Y, Chen X, Wang L (2019) Q-learning with UCB exploration is sample efficient for infinite-horizon MDP. Preprint, submitted January 27, https://arxiv.org/abs/1901.09311.Google Scholar
• [16] Du SS, Kakade SM, Lee JD, Lovett S, Mahajan G, Sun W, Wang R (2021) Bilinear classes: A structural framework for provable generalization in RL. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., PMLR, vol. 139 (PMLR, New York), 2826–2836.Google Scholar
• [17] Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2):95–110.Crossref, Google Scholar
• [18] Gelfand IM, Silverman RA (2000) Calculus of Variations (Courier Corporation, Mineola, NY).Google Scholar
• [19] Gheshlaghi Azar M, Osband I, Munos R (2017) Minimax regret bounds for reinforcement learning. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., PMLR, vol. 70 (PMLR, New York), 263–272.Google Scholar
• [20] Hazan E, Kakade S, Singh K, Van Soest A (2019) Provably efficient maximum entropy exploration. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., PMLR, vol. 97 (PMLR, New York), 2681–2691.Google Scholar
• [21] Huang R, Yang J, Liang Y (2023) Safe exploration incurs nearly no additional sample complexity for reward-free RL. Internat. Conf. Learn. Representations (ICLR).Google Scholar
• [22] Jaksch T, Ortner R, Auer P (2010) Near-optimal regret bounds for reinforcement learning. J. Machine Learn. Res. 11:1563–1600.Google Scholar
• [23] Jin Y, Yang Z, Wang Z (2021) Is pessimism provably efficient for offline RL? Proc. 38th Internat. Conf. Machine Learn., PMLR, vol. 139 (PMLR, New York), 5084–5096.Google Scholar
• [24] Jin C, Allen-Zhu Z, Bubeck S, Jordan MI (2018) Is Q-learning provably efficient? Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Inc., Red Hook, NY), 4863–4873.Google Scholar
• [25] Jin C, Krishnamurthy A, Simchowitz M, Yu T (2020) Reward-free exploration for reinforcement learning. Daumé H III, Singh A, eds. Proc. 37th Internat. Conf. Machine Learn., PMLR, vol. 119 (PMLR, New York), 4870–4879.Google Scholar
• [26] Jin Y, Ren Z, Yang Z, Wang Z (2022) Policy learning “without” overlap: Pessimism and generalized empirical Bernstein’s inequality. Preprint, submitted December 19, https://arxiv.org/abs/2212.09900.Google Scholar
• [27] Jin C, Yang Z, Wang Z, Jordan MI (2020) Provably efficient reinforcement learning with linear function approximation. Abernethy J, Agarwal S, eds. Proc. 33rd Conf. Learn. Theory, PMLR, vol. 125 (PMLR, New York), 2137–2143.Google Scholar
• [28] Kaufmann E, Ménard P, Domingues OD, Jonsson A, Leurent E, Valko M (2021) Adaptive reward-free exploration. Feldman V, Ligett K, Sabato S, eds. Proc. 32nd Internat. Conf. Algorithmic Learn. Theory, PMLR, vol. 132 (PMLR, New York), 865–891.Google Scholar
• [29] Kearns M, Singh S (2002) Near-optimal reinforcement learning in polynomial time. Machine Learn. 49(2):209–232.Crossref, Google Scholar
• [30] Kiefer J, Wolfowitz J (1960) The equivalence of two extremum problems. Canadian J. Math. 12:363–366.Crossref, Google Scholar
• [31] Kumar A, Zhou A, Tucker G, Levine S (2020) Conservative Q-learning for offline reinforcement learning. Adv. Neural Inform. Processing Systems 33:1179–1191.Google Scholar
• [32] Lai TL, Robbins H (1985) Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6(1):4–22.Crossref, Google Scholar
• [33] Lattimore T, Szepesvári C (2020) Bandit Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [34] Levine S, Kumar A, Tucker G, Fu J (2020) Offline reinforcement learning: Tutorial, review, and perspectives on open problems. Preprint, submitted May 4, https://arxiv.org/abs/200501643.Google Scholar
• [35] Li G, Shi L, Chen Y, Chi Y (2023) Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Inform. Inference 12(2):969–1043.Crossref, Google Scholar
• [36] Li G, Wei Y, Chi Y, Chen Y (2024) Breaking the sample size barrier in model-based reinforcement learning with a generative model. Oper. Res. 72(1):203–221.Link, Google Scholar
• [37] Li G, Chen Y, Chi Y, Gu Y, Wei Y (2021) Sample-efficient reinforcement learning is feasible for linearly realizable MDPs with limited revisiting. Adv. Neural Inform. Processing Systems 34:16671–16685.Google Scholar
• [38] Li G, Shi L, Chen Y, Chi Y, Wei Y (2024) Settling the sample complexity of model-based offline reinforcement learning. Ann. Statist. 52(1):233–260.Crossref, Google Scholar
• [39] Li G, Zhan W, Lee JD, Chi Y, Chen Y (2023) Reward-agnostic fine-tuning: Provable statistical benefits of hybrid reinforcement learning. Adv. Neural Inform. Processing Systems 36:55582–55615.Crossref, Google Scholar
• [40] Ménard P, Domingues OD, Shang X, Valko M (2021) UCB momentum Q-learning: Correcting the bias without forgetting. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., PMLR, vol. 139 (PMLR, New York), 7609–7618.Google Scholar
• [41] Ménard P, Domingues OD, Jonsson A, Kaufmann E, Leurent E, Valko M (2021) Fast active learning for pure exploration in reinforcement learning. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., PMLR, vol. 139 (PMLR, New York), 7599–7608.Google Scholar
• [42] Mhammedi Z, Block A, Foster DJ, Rakhlin A (2024) Efficient model-free exploration in low-rank MDPS. Adv. Neural Inform. Processing Systems 36:66782–66817.Google Scholar
• [43] Miryoosefi S, Jin C (2022) A simple reward-free approach to constrained reinforcement learning. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., PMLR, vol. 162 (PMLR, New York), 15666–15698.Google Scholar
• [44] Misra D, Henaff M, Krishnamurthy A, Langford J (2020) Kinematic state abstraction and provably efficient rich-observation reinforcement learning. Daumé H III, Singh A, eds. Proc. 37th Internat. Conf. Machine Learn., PMLR, vol. 119 (PMLR, New York), 6961–6971.Google Scholar
• [45] Peters J, Mulling K, Altun Y (2010) Relative entropy policy search. Fox M, Poole D, eds. Proc. Twenty-Fourth AAAI Conf. Artificial Intelligence (AAAI Press, Menlo Park, CA), 1607–1612.Google Scholar
• [46] Qiao D, Wang Y-X (2023) Near-optimal deployment efficiency in reward-free reinforcement learning with linear function approximation. Internat. Conf. Learn. Representations (ICLR).Google Scholar
• [47] Qiao D, Yin M, Min M, Wang Y-X (2022) Sample-efficient reinforcement learning with loglog(t) switching cost. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., PMLR, vol. 162 (PMLR, New York), 18031–18061.Google Scholar
• [48] Qiu S, Ye J, Wang Z, Yang Z (2021) On reward-free RL with kernel and neural function approximations: Single-agent MDP and Markov game. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., PMLR, vol. 139 (PMLR, New York), 8737–8747.Google Scholar
• [49] Rashidinejad P, Zhu B, Ma C, Jiao J, Russell S (2021) Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Adv. Neural Inform. Processing Systems 34:11702–11716.Google Scholar
• [50] Shi L, Li G, Wei Y, Chen Y, Chi Y (2022) Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., PMLR, vol. 162 (PMLR, New York), 19967–20025.Google Scholar
• [51] Simchowitz M, Jamieson KG (2019) Non-asymptotic gap-dependent regret bounds for tabular mdps. Adv. Neural Inform. Processing Systems 32:1151–1160.Google Scholar
• [52] Vershynin R (2018) High-Dimensional Probability: An Introduction with Applications in Data Science, vol. 47 (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [53] Wagenmaker AJ, Chen Y, Simchowitz M, Du S, Jamieson K (2022) Reward-free RL is no harder than reward-aware RL in linear Markov decision processes. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., PMLR, vol. 162 (PMLR, New York), 22430–22456.Google Scholar
• [54] Wang R, Du SS, Yang L, Salakhutdinov RR (2020) On reward-free reinforcement learning with linear function approximation. Adv. Neural Inform. Processing Systems 33:17816–17826.Google Scholar
• [55] Xie T, Jiang N, Wang H, Xiong C, Bai Y (2021) Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Adv. Neural Inform. Processing Systems 34:27395–27407.Google Scholar
• [56] Xu T, Wang Y, Zou S, Liang Y (2024) Provably efficient offline reinforcement learning with trajectory-wise reward. IEEE Trans. Inform. Theory 70(9):6481–6518.Google Scholar
• [57] Yan Y, Li G, Chen Y, Fan J (2023) The efficacy of pessimism in asynchronous Q-learning. IEEE Trans. Inform. Theory 69(11):7185–7219.Crossref, Google Scholar
• [58] Yan Y, Li G, Chen Y, Fan J (2024) Model-based reinforcement learning for offline zero-sum Markov games. Oper. Res. 72(6):2430–2445.Link, Google Scholar
• [59] Yin M, Wang Y-X (2021) Optimal uniform OPE and model-based offline reinforcement learning in time-homogeneous, reward-free and task-agnostic settings. Adv. Neural Inform. Processing Systems 34:12890–12903.Google Scholar
• [60] Yin M, Wang Y-X (2021) Towards instance-optimal offline reinforcement learning with pessimism. Adv. Neural Inform. Processing Systems 34:4065–4078.Google Scholar
• [61] Yin M, Bai Y, Wang Y-X (2021) Near-optimal offline reinforcement learning via double variance reduction. Adv. Neural Inform. Processing Systems 34:7677–7688.Google Scholar
• [62] Zahavy T, O’Donoghue B, Desjardins G, Singh S (2021) Reward is enough for convex MDPs. Adv. Neural Inform. Processing Systems 34:25746–25759.Google Scholar
• [63] Zanette A, Brunskill E (2019) Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., PMLR, vol. 97 (PMLR, New York), 7304–7312.Google Scholar
• [64] Zanette A, Lazaric A, Kochenderfer MJ, Brunskill E (2020) Provably efficient reward-agnostic navigation with linear value iteration. Adv. Neural Inform. Processing Systems 33:11756–11766.Google Scholar
• [65] Zhang Z, Du S, Ji X (2021) Near optimal reward-free reinforcement learning. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., PMLR, vol. 139 (PMLR, New York), 12402–12412.Google Scholar
• [66] Zhang X, Ma Y, Singla A (2020) Task-agnostic exploration in reinforcement learning. Adv. Neural Inform. Processing Systems 33:11734–11743.Google Scholar
• [67] Zhang W, Zhou D, Gu Q (2021) Reward-free model-based reinforcement learning with linear function approximation. Adv. Neural Inform. Processing Systems 34:1582–1593.Google Scholar
• [68] Zhang Z, Zhou Y, Ji X (2020) Almost optimal model-free reinforcement learning via reference-advantage decomposition. Adv. Neural Inform. Processing Systems 33:15198–15207.Google Scholar
• [69] Zhang Z, Chen Y, Lee J, Du SS (2025) Settling the sample complexity of online reinforcement learning. J. ACM 72(3):1–63.Crossref, Google Scholar
• [70] Zhang X, Song Y, Uehara M, Wang M, Agarwal A, Sun W (2022) Efficient reinforcement learning in block MDPs: A model-free representation learning approach. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., PMLR, vol. 162 (PMLR, New York), 26517–26547.Google Scholar
• [71] Zimin A, Neu G (2013) Online learning in episodic Markovian decision processes by relative entropy policy search. Adv. Neural Inform. Processing Systems 26:1583–1591.Google Scholar