Multiagent Value Iteration Algorithms in Dynamic Programming and Reinforcement Learning
We consider infinite horizon dynamic programming problems, where the control at each stage consists of several distinct decisions, each one made by one of several agents. In an earlier work we introduced a policy iteration algorithm, where the policy improvement is done one-agent-at-a-time in a given order, with knowledge of the choices of the preceding agents in the order. As a result, the amount of computation for each policy improvement grows linearly with the number of agents, as opposed to exponentially for the standard all-agents-at-once method. For the case of a finite-state discounted problem, we showed convergence to an agent-by-agent optimal policy. In this paper, this result is extended to value iteration and optimistic versions of policy iteration, as well as to more general DP problems where the Bellman operator is a contraction mapping, such as stochastic shortest path problems with all policies being proper.
Code (0)
등록된 구현이 없습니다.
Tasks
reinforcement-learningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
On-Line Policy Iteration for Infinite Horizon Dynamic Programming
In this paper we propose an on-line policy iteration (PI) algorithm for finite-state infinite horizon discounted dynamic programming, whereby the policy improvement operation is done on-line, only for the states that are…
Unifying Value Iteration, Advantage Learning, and Dynamic Policy Programming
Approximate dynamic programming algorithms, such as approximate value iteration, have been successfully applied to many complex reinforcement learning tasks, and a better approximate dynamic programming algorithm is expe…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Multiagent Rollout and Policy Iteration for POMDP with Application to Multi-Robot Repair Problems
In this paper we consider infinite horizon discounted dynamic programming problems with finite state and control spaces, partial state observations, and a multiagent structure. We discuss and compare algorithms that simu…
Policy Iteration for Decentralized Control of Markov Decision Processes
Coordination of distributed agents is required for problems arising in many areas, including multi-robot systems, networking and e-commerce. As a formal framework for such problems, we use the decentralized partially obs…
The Value Iteration Algorithm is Not Strongly Polynomial for Discounted Dynamic Programming
This note provides a simple example demonstrating that, if exact computations are allowed, the number of iterations required for the value iteration algorithm to find an optimal policy for discounted dynamic programming …