PAC Bounds for Discounted MDPs
From MaRDI portal
Abstract: We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (MDPs). For the upper bound we make the assumption that each action leads to at most two possible next-states and prove a new bound for a UCRL-style algorithm on the number of time-steps when it is not Probably Approximately Correct (PAC). The new lower bound strengthens previous work by being both more general (it applies to all policies) and tighter. The upper and lower bounds match up to logarithmic factors.
Recommendations
- Near-optimal PAC bounds for discounted MDPs
- scientific article; zbMATH DE number 2089367
- Complexity bounds for approximately solving discounted MDPs by value iterations
- Reinforcement learning in finite MDPs: PAC analysis
- scientific article; zbMATH DE number 4170671
- Global PAC bounds for learning discrete time Markov chains
- Policy Bounds for Markov Decision Processes
- Estimate and approximate policy iteration algorithm for discounted Markov decision models with bounded costs and Borel spaces
- Reduction of discounted continuous-time MDPs with unbounded jump and reward rates to discrete-time total-reward mdps
Cited in
(14)- Global PAC bounds for learning discrete time Markov chains
- Efficient PAC learning for episodic tasks with acyclic state spaces
- Complexity bounds for approximately solving discounted MDPs by value iterations
- Reinforcement learning in finite MDPs: PAC analysis
- Near-optimal regret bounds for reinforcement learning
- scientific article; zbMATH DE number 2089367 (Why is no real title available?)
- Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model
- Near-optimal PAC bounds for discounted MDPs
- Recent advances in reinforcement learning in finance
- Achieving zero constraint violation for concave utility constrained reinforcement learning via primal-dual approach
- Settling the sample complexity of online reinforcement learning
- Slowly changing adversarial bandit algorithms are efficient for discounted MDPs
- Episodic reinforcement learning in finite MDPs: minimax lower bounds revisited
- A model selection approach for corruption robust reinforcement learning
This page was built for publication: PAC Bounds for Discounted MDPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3164829)
