NDLI: Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model

Content Provider	Springer Nature Link
Author	Gheshlaghi Azar, Mohammad Mus, Rémi Kappen, Hilbert J.
Copyright Year	2013
Abstract	We consider the problems of learning the optimal action-value function and the optimal policy in discounted-reward Markov decision processes (MDPs). We prove new PAC bounds on the sample-complexity of two well-known model-based reinforcement learning (RL) algorithms in the presence of a generative model of the MDP: value iteration and policy iteration. The first result indicates that for an MDP with N state-action pairs and the discount factor γ∈[0,1) only O(Nlog(N/δ)/((1−γ)$^{3}$ ε $^{2}$)) state-transition samples are required to find an ε-optimal estimation of the action-value function with the probability (w.p.) 1−δ. Further, we prove that, for small values of ε, an order of O(Nlog(N/δ)/((1−γ)$^{3}$ ε $^{2}$)) samples is required to find an ε-optimal policy w.p. 1−δ. We also prove a matching lower bound of Θ(Nlog(N/δ)/((1−γ)$^{3}$ ε $^{2}$)) on the sample complexity of estimating the optimal action-value function with ε accuracy. To the best of our knowledge, this is the first minimax result on the sample complexity of RL: the upper bounds match the lower bound in terms of N, ε, δ and 1/(1−γ) up to a constant factor. Also, both our lower bound and upper bound improve on the state-of-the-art in terms of their dependence on 1/(1−γ).
Starting Page	325
Ending Page	349
Page Count	25
File Format	PDF
ISSN	08856125
Journal	Machine Learning
Volume Number	91
Issue Number	3
e-ISSN	15730565
Language	English
Publisher	Springer US
Publisher Date	2013-05-14
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Sample complexity Markov decision processes Reinforcement learning Learning theory Artificial Intelligence (incl. Robotics) Control, Robotics, Mechatronics Computing Methodologies Simulation and Modeling Language Translation and Linguistics
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Model selection in reinforcement learning

Bounds on the sample complexity for private learning and private data release

Hybrid least-squares algorithms for approximate policy evaluation

Policy gradient in Lipschitz Markov Decision Processes

Improving reinforcement learning by using sequence trees

Probabilistic inference for determining options in reinforcement learning

Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model

Learning rotations with little regret

TEXPLORE: real-time sample-efficient reinforcement learning for robots

Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model

Similar Documents

Model selection in reinforcement learning

Bounds on the sample complexity for private learning and private data release

Hybrid least-squares algorithms for approximate policy evaluation

Policy gradient in Lipschitz Markov Decision Processes

Improving reinforcement learning by using sequence trees

Probabilistic inference for determining options in reinforcement learning

Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model

Learning rotations with little regret

TEXPLORE: real-time sample-efficient reinforcement learning for robots

Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model