A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games
Optimal policies in standard MDPs can be obtained using either value iteration or policy iteration. However, in the case of zero-sum Markov games, there is no efficient policy iteration algorithm; e.g., it has been shown that one has to solve Omega(1/(1-alpha)) MDPs, where alpha is the discount factor, to implement the only known convergent version of policy iteration. Another algorithm, called naive policy iteration, is easy to implement but is only provably convergent under very restrictive assumptions. Prior attempts to fix naive policy iteration algorithm have several limitations. Here, we show that a simple variant of naive policy iteration for games converges exponentially fast. The only addition we propose to naive policy iteration is the use of lookahead policies, which are anyway used in practical algorithms. We further show that lookahead can be implemented efficiently in the function approximation setting of linear Markov games, which are the counterpart of the much-studied linear MDPs. We illustrate the application of our algorithm by providing bounds for policy-based RL (reinforcement learning) algorithms. We extend the results to the function approximation setting.
Code (0)
등록된 구현이 없습니다.
Tasks
Model-based Reinforcement LearningMulti-agent Reinforcement Learningreinforcement-learningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Reinforcement Learning: Tutorial and Survey
This is a tutorial and survey paper on reinforcement learning, from fundamental reinforcement learning to deep reinforcement learning. It starts with introducing the elements of reinforcement learning. Then, Markov decis…
Deep Reinforcement LearningGeneral Reinforcement LearningQ-Learningreinforcement-learning+3A Sharp Analysis of Model-based Reinforcement Learning with Self-Play
Model-based algorithms -- algorithms that explore the environment through building and utilizing an estimated model -- are widely used in reinforcement learning practice and theoretically shown to achieve optimal sample …
Model-based Reinforcement LearningMulti-agent Reinforcement Learningreinforcement-learningReinforcement Learning+1Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games
Policy-based methods with function approximation are widely used for solving two-player zero-sum games with large state and/or action spaces. However, it remains elusive how to obtain optimization and statistical guarant…
Policy Gradient MethodsVocal Bursts Valence PredictionAdversarial Policy Gradient for Alternating Markov Games
Policy gradient reinforcement learning has been applied to two-player alternate-turn zero-sum games, e.g., in AlphaGo, self-play REINFORCE was used to improve the neural net model after supervised learning. In this paper…
Policy Gradient MethodsReinforcement LearningAlphaSnake: Policy Iteration on a Nondeterministic NP-hard Markov Decision Process
Reinforcement learning has recently been used to approach well-known NP-hard combinatorial problems in graph theory. Among these problems, Hamiltonian cycle problems are exceptionally difficult to analyze, even when rest…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)