Anderson Acceleration for Partially Observable Markov Decision Processes: A Maximum Entropy Approach
Partially observable Markov decision processes (POMDPs) is a rich mathematical framework that embraces a large class of complex sequential decision-making problems under uncertainty with limited observations. However, the complexity of POMDPs poses various computational challenges, motivating the need for an efficient algorithm that rapidly finds a good enough suboptimal solution. In this paper, we propose a novel accelerated offline POMDP algorithm exploiting Anderson acceleration (AA) that is capable of efficiently solving fixed-point problems using previous solution estimates. Our algorithm is based on the Q-function approximation (QMDP) method to alleviate the scalability issue inherent in POMDPs. Inspired by the quasi-Newton interpretation of AA, we propose a maximum entropy variant of QMDP, which we call soft QMDP, to fully benefit from AA. We prove that the overall algorithm converges to the suboptimal solution obtained by soft QMDP. Our algorithm can also be implemented in a model-free manner using simulation data. Provable error bounds on the residual and the solution are provided to examine how the simulation errors are propagated through the proposed algorithm. Finally, the performance of our algorithm is tested on several benchmark problems. According to the results of our experiments, the proposed algorithm converges significantly faster without degrading the solution quality compared to its standard counterparts.
Code (1)
Tasks
Decision MakingSequential Decision MakingSimilar Papers 제목 키워드 기반
On Anderson acceleration for partially observable Markov decision processes
This paper proposes an accelerated method for approximately solving partially observable Markov decision process (POMDP) problems offline. Our method carefully combines two existing tools: Anderson acceleration (AA) and …
Decision Making for Autonomous Vehicles
This paper is on decision making of autonomous vehicles for handling roundabouts. The round intersection is introduced first followed by the Markov Decision Processes (MDP), the Partially Observable Markov Decision Proce…
Autonomous VehiclesDecision MakingDynamic deep-reinforcement-learning algorithm in Partially Observed Markov Decision Processes
Reinforcement learning has been greatly improved in recent studies and an increased interest in real-world implementation has emerged in recent years. In many cases, due to the non-static disturbances, it becomes challen…
Deep Reinforcement Learningreinforcement-learningReinforcement LearningPoint-Based Methods for Model Checking in Partially Observable Markov Decision Processes
Autonomous systems are often required to operate in partially observable environments. They must reliably execute a specified objective even with incomplete information about the state of the environment. We propose a me…
The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processes
We study the geometry of feasible value functions in infinite-horizon partially observable Markov decision processes (POMDPs) under memoryless stochastic policies. Our main contribution is a characterization of the feasi…