Primal-Dual $\pi$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems

Abstract

Consider the problem of approximating the optimal policy of a Markov decision process (MDP) by sampling state transitions. In contrast to existing reinforcement learning methods that are based on successive approximations to the nonlinear Bellman equation, we propose a Primal-Dual $\pi$ Learning method in light of the linear duality between the value and policy. The $\pi$ learning method is model-free and makes primal-dual updates to the policy and value vectors as new data are revealed. For infinite-horizon undiscounted Markov decision process with finite state space $S$ and finite action space $A$, the $\pi$ learning method finds an $\epsilon$-optimal policy using the following number of sample transitions $$\tilde{O}(\frac{(\tau \cdot t_{mix}^{\ast }{)}^2|S||A|}{{\epsilon }^2}),$$ where $t_{mix}^{\ast }$ is an upper bound of mixing times across all policies and $\tau$ is a parameter characterizing the range of stationary distributions across policies. The $\pi$ learning method also applies to the computational problem of MDP where the transition probabilities and rewards are explicitly given as the input. In the case where each state transition can be sampled in $\tilde{O}(1)$ time, the $\pi$ learning method gives a sublinear-time algorithm for solving the averaged-reward MDP.

References in corpus (5)

• On the Complexity of Policy Iteration
• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
• Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time
• Lower Bound On the Computational Complexity of Discounted Markov Decision Problems
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes

Cited by in corpus (18)

• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Average-reward model-free reinforcement learning: a systematic review and literature mapping
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
• Quantum Algorithms for Reinforcement Learning with a Generative Model
• Ecological Reinforcement Learning
• Black-box Off-policy Estimation for Infinite-Horizon Reinforcement Learning
• Cautious Reinforcement Learning via Distributional Risk in the Dual Domain
• Deep Primal-Dual Reinforcement Learning: Accelerating Actor-Critic using Bellman Duality
• Generalization Bounds for Stochastic Saddle Point Problems
• A Reduction from Reinforcement Learning to No-Regret Online Learning
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
• Large Scale Markov Decision Processes with Changing Rewards
• On Sample Complexity of Projection-Free Primal-Dual Methods for Learning Mixture Policies in Markov Decision Processes
• Near Optimal Policy Optimization via REPS
• Voting-Based Multi-Agent Reinforcement Learning for Intelligent IoT
• Active Information Acquisition for Linear Optimization