Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes

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

zbMATH Keywords

Markov decision processesvalue iterationlinear programming algorithm

Mathematics Subject Classification ID

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