Literature

Literature

The results of the literature behind LMLExplore and its roadmaps

266results with a declaration
28works cited
636declarations citing them
27%of the roadmaps' results

How the links are made

A declaration of LMLExplore is linked to a result of the literature when it cites it, as [GK16, Theorem 14], in its docstring or in the list of main statements of its module. A link says that the declaration and the result correspond, not how: the declaration may state the result exactly, more generally, or one part of it, or be a step of its proof.

The roadmaps of LMLRoadmaps cite the results that LMLExplore aims at. A result that they cite and no declaration does is not linked yet: it may be formalized without the citation, or not at all.

The roadmaps

The 655 results that the roadmaps cite, and how many have a declaration citing them.

At LMLExplore commit faf2c0906563 and LMLRoadmaps commit 468f19f45fae. Sections, chapters, figures and tables count as places, not results.
RoadmapResults cited With a declaration
Bandits11289
Generalization1716
Identification9144
OnlineLearning2276
Refactors88
ReinforcementLearning23245
All roadmaps655179

The works

Each work with its results, by number of results. Each declaration links to its page on the referee site and to its source.

[Ora] Francesco Orabona, Online Learning: A Modern Introduction Using Convex Optimization, 2026 · link · arXiv:1912.13213v10

10 results with a declaration · the roadmaps cite 230: 7 of 230 have a declaration

[LS] Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, Cambridge University Press, 2020 · link · doi:10.1017/9781108571401

117 results with a declaration · the roadmaps cite 111: 84 of 111 have a declaration

[P] Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994 · link · doi:10.1002/9780470316887

28 results with a declaration · the roadmaps cite 79: 25 of 79 have a declaration

[DK19] Rémy Degenne and Wouter M. Koolen, Pure Exploration with Multiple Correct Answers, Advances in Neural Information Processing Systems 32 (NeurIPS), 2019 · link · arXiv:1902.03475

15 results with a declaration · the roadmaps cite 28: 14 of 28 have a declaration

[AJKS] Alekh Agarwal, Nan Jiang, Sham M. Kakade and Wen Sun, Reinforcement Learning: Theory and Algorithms, 2022 · link

12 results with a declaration · the roadmaps cite 25: 11 of 25 have a declaration

[GK16] Aurélien Garivier and Emilie Kaufmann, Optimal Best Arm Identification with Fixed Confidence, Proceedings of the 29th Conference on Learning Theory (COLT), 2016 · link · arXiv:1602.04589

19 results with a declaration · the roadmaps cite 17: 13 of 17 have a declaration

[AKLM21] A. Agarwal, S. M. Kakade, J. D. Lee and G. Mahajan, On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift, 2021 · link · arXiv:1908.00261

0 results with a declaration · the roadmaps cite 11: 0 of 11 have a declaration

[D23] R. Degenne, On the Existence of a Complexity in Fixed Budget Bandit Identification, Proceedings of the Conference on Learning Theory (COLT), 2023 · link · arXiv:2303.09468

9 results with a declaration · the roadmaps cite 2: 1 of 2 have a declaration

[DKM19] Rémy Degenne, Wouter M. Koolen and Pierre Ménard, Non-Asymptotic Pure Exploration by Solving Games, Advances in Neural Information Processing Systems 32 (NeurIPS), 2019 · link · arXiv:1906.10431

4 results with a declaration · the roadmaps cite 8: 2 of 8 have a declaration

[BRS18] J. Bhandari, D. Russo and R. Singal, A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation, Proceedings of the Conference on Learning Theory (COLT), 2018 · link · arXiv:1806.02450

0 results with a declaration · the roadmaps cite 7: 0 of 7 have a declaration

[JYW21] Ying Jin, Zhuoran Yang and Zhaoran Wang, Is Pessimism Provably Efficient for Offline RL?, Proceedings of the 38th International Conference on Machine Learning (ICML), 2021 · link · arXiv:2012.15085

4 results with a declaration · the roadmaps cite 5: 2 of 5 have a declaration

[KCG16] Emilie Kaufmann, Olivier Cappé and Aurélien Garivier, On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models, Journal of Machine Learning Research, 2016 · link · arXiv:1407.4443

3 results with a declaration · the roadmaps cite 6: 2 of 6 have a declaration

[MXSS20] J. Mei, C. Xiao, Cs. Szepesvári and D. Schuurmans, On the Global Convergence Rates of Softmax Policy Gradient Methods, Proceedings of the International Conference on Machine Learning (ICML), 2020 · link · arXiv:2005.06392

0 results with a declaration · the roadmaps cite 7: 0 of 7 have a declaration

[AKY20] A. Agarwal, S. Kakade and L. F. Yang, Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal, Proceedings of the Conference on Learning Theory (COLT), 2020 · link · arXiv:1906.03804

5 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[KK13] Emilie Kaufmann and Shivaram Kalyanakrishnan, Information Complexity in Bandit Subset Selection, Proceedings of the 26th Conference on Learning Theory (COLT), 2013 · link

4 results with a declaration · the roadmaps cite 2: 0 of 2 have a declaration

[MDJKLV21] P. Ménard, O. D. Domingues, A. Jonsson, E. Kaufmann, E. Leurent and M. Valko, Fast active learning for pure exploration in reinforcement learning, Proceedings of the International Conference on Machine Learning (ICML), 2021 · link · arXiv:2007.13442

0 results with a declaration · the roadmaps cite 6: 0 of 6 have a declaration

[EMM02] Eyal Even-Dar, Shie Mannor and Yishay Mansour, PAC Bounds for Multi-armed Bandit and Markov Decision Processes, Computational Learning Theory (COLT 2002), 2002 · link · doi:10.1007/3-540-45435-7_18

5 results with a declaration · the roadmaps cite 4: 4 of 4 have a declaration

[JOA10] Thomas Jaksch, Ronald Ortner and Peter Auer, Near-optimal Regret Bounds for Reinforcement Learning, Journal of Machine Learning Research, 2010 · link

1 result with a declaration · the roadmaps cite 5: 1 of 5 have a declaration

[JYWJ20] C. Jin, Z. Yang, Z. Wang and M. I. Jordan, Provably Efficient Reinforcement Learning with Linear Function Approximation, Proceedings of the Conference on Learning Theory (COLT), 2020 · link · arXiv:1907.05388

0 results with a declaration · the roadmaps cite 5: 0 of 5 have a declaration

[Neu15] G. Neu, Explore no more: Improved high-probability regret bounds for non-stochastic bandits, Advances in Neural Information Processing Systems (NeurIPS), 2015 · link · arXiv:1506.03271

5 results with a declaration · the roadmaps cite 3: 3 of 3 have a declaration

[ZCLD24] Z. Zhang, Y. Chen, J. D. Lee and S. S. Du, Settling the Sample Complexity of Online Reinforcement Learning, Proceedings of the Conference on Learning Theory (COLT), 2024 · link · arXiv:2307.13586

0 results with a declaration · the roadmaps cite 5: 0 of 5 have a declaration

[CT] Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, Wiley, 2006 · link · doi:10.1002/047174882X

1 result with a declaration · the roadmaps cite 3: 0 of 3 have a declaration

[GC11] A. Garivier and O. Cappé, The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond, Proceedings of the Conference on Learning Theory (COLT), 2011 · link · arXiv:1102.2490

2 results with a declaration · the roadmaps cite 3: 1 of 3 have a declaration

[JJLSY20] C. Jin, T. Jin, H. Luo, S. Sra and T. Yu, Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition, Proceedings of the International Conference on Machine Learning (ICML), 2020 · link · arXiv:1912.01192

0 results with a declaration · the roadmaps cite 4: 0 of 4 have a declaration

[KKS13] Zohar Karnin, Tomer Koren and Oren Somekh, Almost Optimal Exploration in Multi-Armed Bandits, Proceedings of the 30th International Conference on Machine Learning (ICML), 2013 · link

4 results with a declaration

[KTAS12] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer and Peter Stone, PAC Subset Selection in Stochastic Multi-armed Bandits, Proceedings of the 29th International Conference on Machine Learning (ICML), 2012 · link

3 results with a declaration · the roadmaps cite 2: 1 of 2 have a declaration

[Kal21] Olav Kallenberg, Foundations of Modern Probability, Springer International Publishing, 2021 · link · doi:10.1007/978-3-030-61871-1

0 results with a declaration · the roadmaps cite 4: 0 of 4 have a declaration

[TVR97] J.N. Tsitsiklis and B. Van Roy, An analysis of temporal-difference learning with function approximation, IEEE Transactions on Automatic Control, 1997 · link · doi:10.1109/9.580874

0 results with a declaration · the roadmaps cite 4: 0 of 4 have a declaration

[ZC24] Matthew Zurek and Yudong Chen, Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs, Advances in Neural Information Processing Systems 37, 2024 · link · arXiv:2403.11477 · doi:10.52202/079017-1055

0 results with a declaration · the roadmaps cite 4: 0 of 4 have a declaration

[ZJD21] Z. Zhang, X. Ji and S. S. Du, Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon, Proceedings of the Conference on Learning Theory (COLT), 2021 · link · arXiv:2009.13503

0 results with a declaration · the roadmaps cite 4: 0 of 4 have a declaration

[DMKV21] O. D. Domingues, P. Ménard, E. Kaufmann and M. Valko, Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited, Proceedings of the International Conference on Algorithmic Learning Theory (ALT), 2021 · link · arXiv:2010.03531

0 results with a declaration · the roadmaps cite 3: 0 of 3 have a declaration

[JDK23] Marc Jourdan, Rémy Degenne and Emilie Kaufmann, Dealing with Unknown Variances in Best-Arm Identification, Proceedings of the 34th International Conference on Algorithmic Learning Theory (ALT), 2023 · link · arXiv:2210.00974

3 results with a declaration · the roadmaps cite 1: 1 of 1 have a declaration

[JDK23b] M. Jourdan, R. Degenne and E. Kaufmann, An ε-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond, Advances in Neural Information Processing Systems (NeurIPS), 2023 · link · arXiv:2305.16041

0 results with a declaration · the roadmaps cite 3: 0 of 3 have a declaration

[JS21] Y. Jin and A. Sidford, Towards Tight Bounds on the Sample Complexity of Average-reward MDPs, Proceedings of the International Conference on Machine Learning (ICML), 2021 · link · arXiv:2106.07046

0 results with a declaration · the roadmaps cite 3: 0 of 3 have a declaration

[LPW17] D. A. Levin, Y. Peres and E. L. Wilmer, Markov Chains and Mixing Times, American Mathematical Society, 2017 · link · doi:10.1090/mbk/107

0 results with a declaration · the roadmaps cite 3: 0 of 3 have a declaration

[Tsi94] John N. Tsitsiklis, Asynchronous Stochastic Approximation and Q-Learning, Machine Learning, 1994 · link · doi:10.1023/a:1022689125041

0 results with a declaration · the roadmaps cite 3: 0 of 3 have a declaration

[Xiao22] L. Xiao, On the Convergence Rates of Policy Gradient Methods, Journal of Machine Learning Research, 2022 · link · arXiv:2201.07443

0 results with a declaration · the roadmaps cite 3: 0 of 3 have a declaration

[BCB12] Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Foundations and Trends® in Machine Learning, 2012 · link · doi:10.1561/2200000024

2 results with a declaration · the roadmaps cite 1: 1 of 1 have a declaration

[BLM13] Stéphane Boucheron, Gábor Lugosi and Pascal Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, 2013 · link · doi:10.1093/acprof:oso/9780199535255.001.0001

2 results with a declaration · the roadmaps cite 2: 2 of 2 have a declaration

[CCCWC22] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei and Yuejie Chi, Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization, Operations Research, 2022 · link · arXiv:2007.06558 · doi:10.1287/opre.2021.2151

0 results with a declaration · the roadmaps cite 2: 0 of 2 have a declaration

[FJJR19] T. Fiez, L. Jain, K. Jamieson and L. Ratliff, Sequential Experimental Design for Transductive Linear Bandits, Advances in Neural Information Processing Systems (NeurIPS), 2019 · link · arXiv:1906.08399

0 results with a declaration · the roadmaps cite 2: 0 of 2 have a declaration

[JABJ18] Chi Jin, Zeyuan Allen-Zhu, Sébastien Bubeck and Michael I. Jordan, Is Q-learning Provably Efficient?, Advances in Neural Information Processing Systems 31 (NeurIPS), 2018 · link · arXiv:1807.03765

1 result with a declaration · the roadmaps cite 2: 1 of 2 have a declaration

[JD23] Marc Jourdan and Rémy Degenne, Non-Asymptotic Analysis of a UCB-based Top Two Algorithm, Advances in Neural Information Processing Systems 36, 2023 · link · doi:10.52202/075280-3019

0 results with a declaration · the roadmaps cite 2: 0 of 2 have a declaration

[JPR23] Emmeran Johnson, Ciara Pike-Burke and Patrick Rebeschini, Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes, Advances in Neural Information Processing Systems 36, 2023 · link · arXiv:2302.11381 · doi:10.52202/075280-3343

0 results with a declaration · the roadmaps cite 2: 0 of 2 have a declaration

[KK21] E. Kaufmann and W. M. Koolen, Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals, Journal of Machine Learning Research, 2021 · link · arXiv:1811.11419

0 results with a declaration · the roadmaps cite 2: 0 of 2 have a declaration

[LSCCW24] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi and Yuting Wei, Settling the sample complexity of model-based offline reinforcement learning, The Annals of Statistics, 2024 · link · arXiv:2204.05275 · doi:10.1214/23-aos2342

0 results with a declaration · the roadmaps cite 2: 0 of 2 have a declaration

[MT04] Shie Mannor and John N. Tsitsiklis, The Sample Complexity of Exploration in the Multi-Armed Bandit Problem, Journal of Machine Learning Research, 2004 · link

2 results with a declaration · the roadmaps cite 1: 1 of 1 have a declaration

[Nor97] J. R. Norris, Markov Chains, Cambridge University Press, 1997 · link · doi:10.1017/cbo9780511810633

0 results with a declaration · the roadmaps cite 2: 0 of 2 have a declaration

[R16] Daniel Russo, Simple Bayesian Algorithms for Best-Arm Identification, 2016 · link · arXiv:1602.08448v4

2 results with a declaration

[RM19] A. Rosenberg and Y. Mansour, Online Convex Optimization in Adversarial Markov Decision Processes, Proceedings of the International Conference on Machine Learning (ICML), 2019 · link · arXiv:1905.07773

0 results with a declaration · the roadmaps cite 2: 0 of 2 have a declaration

[RZMJR21] P. Rashidinejad, B. Zhu, C. Ma, J. Jiao and S. Russell, Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism, Advances in Neural Information Processing Systems (NeurIPS), 2021 · link · arXiv:2103.12021

0 results with a declaration · the roadmaps cite 2: 0 of 2 have a declaration

[ABM10] Jean-Yves Audibert, Sébastien Bubeck and Rémi Munos, Best Arm Identification in Multi-Armed Bandits, Proceedings of the 23rd Conference on Learning Theory (COLT), 2010 · link

1 result with a declaration

[AMK13] M. G. Azar, R. Munos and H. J. Kappen, Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model, Machine Learning, 2013 · link · doi:10.1007/s10994-013-5368-1

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[AMS09] Jean-Yves Audibert, Rémi Munos and Csaba Szepesvári, Exploration–exploitation tradeoff using variance estimates in multi-armed bandits, Theoretical Computer Science, 2009 · link · doi:10.1016/j.tcs.2009.01.016

1 result with a declaration · the roadmaps cite 1: 1 of 1 have a declaration

[AYPS11] Y. Abbasi-Yadkori, D. Pál and Cs. Szepesvári, Improved Algorithms for Linear Stochastic Bandits, Advances in Neural Information Processing Systems (NeurIPS), 2011 · link

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[DZ98] Amir Dembo and Ofer Zeitouni, Large Deviations Techniques and Applications, Springer New York, 1998 · link · doi:10.1007/978-1-4612-5320-4

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[GMS19] Aurélien Garivier, Pierre Ménard and Gilles Stoltz, Explore First, Exploit Next: The True Shape of Regret in Bandit Problems, Mathematics of Operations Research, 2019 · link · arXiv:1602.07182 · doi:10.1287/moor.2017.0928

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[JKSY20] C. Jin, A. Krishnamurthy, M. Simchowitz and T. Yu, Reward-Free Exploration for Reinforcement Learning, Proceedings of the International Conference on Machine Learning (ICML), 2020 · link · arXiv:2002.02794

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[KKM13] N. Korda, E. Kaufmann and R. Munos, Thompson Sampling for 1-Dimensional Exponential Family Bandits, Advances in Neural Information Processing Systems (NeurIPS), 2013 · link · arXiv:1307.3400

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[KNS16] Hamed Karimi, Julie Nutini and Mark Schmidt, Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition, Machine Learning and Knowledge Discovery in Databases, 2016 · link · arXiv:1608.04636 · doi:10.1007/978-3-319-46128-1_50

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[LWCGC24] Gen Li, Yuting Wei, Yuejie Chi and Yuxin Chen, Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model, Operations Research, 2024 · link · arXiv:2005.12900 · doi:10.1287/opre.2023.2451

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[Lan23] Guanghui Lan, Policy mirror descent for reinforcement learning: linear convergence, new sampling complexity, and generalized problem classes, Mathematical Programming, 2023 · link · arXiv:2102.00135 · doi:10.1007/s10107-022-01816-5

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[Nes18] Yurii Nesterov, Lectures on Convex Optimization, Springer International Publishing, 2018 · link · doi:10.1007/978-3-319-91578-4

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[QKR17] C. Qin, D. Klabjan and D. Russo, Improving the Expected Improvement Algorithm, Advances in Neural Information Processing Systems (NeurIPS), 2017 · link · arXiv:1705.10033

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[RS71] H. Robbins and D. Siegmund, A Convergence Theorem for Non Negative Almost Supermartingales and Some Applications, Optimizing Methods in Statistics, 1971 · link · doi:10.1016/B978-0-12-604550-5.50015-8

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[SdHMKV20] X. Shang, R. de Heide, P. Ménard, E. Kaufmann and M. Valko, Fixed-Confidence Guarantees for Bayesian Best-Arm Identification, Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2020 · link · arXiv:1910.10945

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[WJLSJ20] C.-Y. Wei, M. Jafarnia-Jahromi, H. Luo, H. Sharma and R. Jain, Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes, Proceedings of the International Conference on Machine Learning (ICML), 2020 · link · arXiv:1910.07072

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

[WOSVW03] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdú and Marcelo J. Weinberger, Inequalities for the L1 Deviation of the Empirical Distribution, HP Laboratories, 2003

1 result with a declaration · the roadmaps cite 1: 1 of 1 have a declaration

[WTP21] P.-A. Wang, R.-C. Tzeng and A. Proutière, Fast Pure Exploration via Frank-Wolfe, Advances in Neural Information Processing Systems (NeurIPS), 2021 · link

0 results with a declaration · the roadmaps cite 1: 0 of 1 have a declaration

The data

The links are published as annotations.jsonl (1238 annotations), in the Literature Links format. They have no relation.

The subject of each annotation is a numbered result of a work. Its location has "profile": "https://leanmachinelearning.org/LMLExplore/literature/#numbered-item", a label and optionally a part. label is the result as the work prints it, such as Theorem 14, Lemma A.1, Section 4.3, or (8.2) for an equation, in the numbering of the revision that the end's version names, or of the published work when it names none. part narrows it, such as (a). An annotation whose kind is proof is about the proof of the result.

The extension org.leanmachinelearning.lmlroadmaps of an annotation names the LMLRoadmaps items that cite its result, as Identification 5.2, the second target of the layer 5 of the Identification roadmap, with the commit of LMLRoadmaps they were read at. An annotation whose object is empty records a result that the roadmaps cite and no declaration does.