Efficient algorithms for budget-constrained markov decision processes

Constantine Caramanis*, Nedialko B. Dimitrov, David P. Morton

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Discounted, discrete-time, discrete state-space, discrete action-space Markov decision processes (MDPs) form a classical topic in control, game theory, and learning, and as a result are widely applied, increasingly, in very large-scale applications. Many algorithms have been developed to solve large-scale MDPs. Algorithms based on value iteration are particularly popular, as they are more efficient than the generic linear programming approach, by an order of magnitude in the number of states of the MDP. Yet in the case of budget constrained MDPs, no more efficient algorithm than linear programming is known. The theoretically slower running times of linear programming may limit the scalability of constrained MDPs piratically; while, theoretically, it invites the question of whether the increase is somehow intrinsic. In this technical note we show that it is not, and provide two algorithms for budget-constrained MDPs that are as efficient as value iteration. Denoting the running time of value iteration by VI, and the magnitude of the input by $U$, for an MDP with m expected budget constraints our first algorithm runs in time O(poly(m, log U)VI). Given a pre-specified degree of precision, η, for satisfying the budget constraints, our second algorithm runs in time O(log mpoly log U)(1/η2VI), but may produce solutions that overutilize each of the m budgets by a multiplicative factor of 1+η. In fact, one can substitute value iteration with any algorithm, possibly specially designed for a specific MDP, that solves the MDP quickly to achieve similar theoretical guarantees. Both algorithms restrict attention to constrained infinite-horizon MDPs under discounted costs.

Original languageEnglish (US)
Article number6780601
Pages (from-to)2813-2817
Number of pages5
JournalIEEE Transactions on Automatic Control
Volume59
Issue number10
DOIs
StatePublished - Oct 1 2014

Keywords

  • Markov decision processes (MDPs)

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Efficient algorithms for budget-constrained markov decision processes'. Together they form a unique fingerprint.

Cite this