Faster Fixed-Point Methods for Multichain MDPs
We study value-iteration (VI) algorithms for solving general (a.k.a. multichain) Markov decision processes (MDPs) under the average-reward criterion, a fundamental but theoretically challenging setting. Beyond the difficulties inherent to all average-reward problems posed by the lack of contractivity and non-uniqueness of solutions to the Bellman operator, in the multichain setting an optimal policy must solve the navigation subproblem of steering towards the best connected component, in addition to optimizing long-run performance within each component. We develop algorithms which better solve this navigational subproblem in order to achieve faster convergence for multichain MDPs, obtaining improved rates of convergence and sharper measures of complexity relative to prior work. Many key components of our results are of potential independent interest, including novel connections between average-reward and discounted problems, optimal fixed-point methods for discounted VI which extend to general Banach spaces, new sublinear convergence rates for the discounted value error, and refined suboptimality decompositions for multichain MDPs. Overall our results yield faster convergence rates for discounted and average-reward problems and expand the theoretical foundations of VI approaches.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs
We study the sample complexity of learning an $\varepsilon$-optimal policy in an average-reward Markov decision process (MDP) under a generative model. For weakly communicating MDPs, we establish the complexity bound $\w…
Steady-State Planning in Expected Reward Multichain MDPs
The planning domain has experienced increased interest in the formal synthesis of decision-making policies. This formal synthesis typically entails finding a policy which satisfies formal specifications in the form of so…
Decision MakingEffect of Outlier Removal from Temporal ASF Corrections on Multichain Loran Positioning Accuracy
The widely used global navigation satellite systems (GNSSs) are vulnerable to radio frequency interference (RFI). Long-range navigation (Loran), a terrestrial navigation system, can compensate for this weakness; however,…
ISC-POMDPs: Partially Observed Markov Decision Processes with Initial-State Dependent Costs
We introduce a class of partially observed Markov decision processes (POMDPs) with costs that can depend on both the value and (future) uncertainty associated with the initial state. These Initial-State Cost POMDPs (ISC-…
Robot NavigationScaling Up Robust MDPs by Reinforcement Learning
We consider large-scale Markov decision processes (MDPs) with parameter uncertainty, under the robust MDP paradigm. Previous studies showed that robust MDPs, based on a minimax approach to handle uncertainty, can be solv…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)