Memoryless Exact Solutions for Deterministic MDPs with Sparse Rewards
We propose an algorithm for deterministic continuous Markov Decision Processes with sparse rewards that computes the optimal policy exactly with no dependency on the size of the state space. The algorithm has time complexity of $O( |R|^3 \times |A|^2 )$ and memory complexity of $O( |R| \times |A| )$, where $|R|$ is the number of reward sources and $|A|$ is the number of actions. Furthermore, we describe a companion algorithm that can follow the optimal policy from any initial state without computing the entire value function, instead computing on-demand the value of states as they are needed. The algorithm to solve the MDP does not depend on the size of the state space for either time or memory complexity, and the ability to follow the optimal policy is linear in time and space with the path length of following the optimal policy from the initial state. We demonstrate the algorithm operation side by side with value iteration on tractable MDPs.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fast Online Exact Solutions for Deterministic MDPs with Sparse Rewards
Markov Decision Processes (MDPs) are a mathematical framework for modeling sequential decision making under uncertainty. The classical approaches for solving MDPs are well known and have been widely studied, some of whic…
Decision MakingDecision Making Under UncertaintySequential Decision MakingGeometry and Determinism of Optimal Stationary Control in Partially Observable Markov Decision Processes
It is well known that for any finite state Markov decision process (MDP) there is a memoryless deterministic policy that maximizes the expected reward. For partially observable Markov decision processes (POMDPs), optimal…
Computing the Exact Pareto Front in Average-Cost Multi-Objective Markov Decision Processes
Many communication and control problems are cast as multi-objective Markov decision processes (MOMDPs). The complete solution to an MOMDP is the Pareto front. Much of the literature approximates this front via scalarizat…
Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs
We study countably infinite Markov decision processes (MDPs) with real-valued transition rewards. Every infinite run induces the following sequences of payoffs: 1. Point payoff (the sequence of directly seen transition r…
Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs
We study countably infinite Markov decision processes (MDPs) with real-valued transition rewards. Every infinite run induces the following sequences of payoffs: 1. Point payoff (the sequence of directly seen transition r…