Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
From MaRDI portal
Publication:4607932
DOI10.1002/nav.21992zbMath1403.68386arXiv1710.09988MaRDI QIDQ4607932
Unnamed Author, Unnamed Author, Yinyu Ye, Aaron Sidford
Publication date: 15 March 2018
Published in: Naval Research Logistics (NRL) (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1710.09988
Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Markov and semi-Markov decision processes (90C40) Approximation algorithms (68W25)
Related Items (5)
Unnamed Item ⋮ Randomized Linear Programming Solves the Markov Decision Problem in Nearly Linear (Sometimes Sublinear) Time ⋮ On the Complexity of Value Iteration ⋮ Unnamed Item ⋮ On the computational efficiency of catalyst accelerated coordinate descent
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model
- A sparse sampling algorithm for near-optimal planning in large Markov decision processes
- The value iteration algorithm is not strongly polynomial for discounted dynamic programming
- Solving H-horizon, stationary Markov decision problems in time proportional to log (H)
- The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
- PAC Bounds for Discounted MDPs
- Probability Inequalities for Sums of Bounded Random Variables
- Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor
- A New Complexity Result on Solving the Markov Decision Problem
This page was built for publication: Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
