Linear Programming for Large-Scale Markov Decision Problems

By Alan Malek, Yasin Abbasi-Yadkori, Peter L. Bartlett. 2014

48 citations recorded by the source corpus.

We consider the problem of controlling a Markov decision process (MDP) with a large state space, so as to minimize average cost. Since it is intractable to compete with the optimal policy for large scale problems, we pursue the more modest goal of competing with a low-dimensional family of policies. We use the dual linear programming formulation of the MDP average cost problem, in which the variable is a stationary distribution over state-action pairs, and we consider a neighborhood of a low-dimensional subset of the set of stationary distributions (defined in terms of state-action features) as the comparison class. We propose a technique based on stochastic convex optimization and give bounds that show that the performance of our algorithm approaches the best achievable by any policy in the comparison class. Most importantly, this result depends on the size of the comparison class, but not on the size of the state space. Preliminary experiments show the effectiveness of the proposed algorithm in a queuing application.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Bo Dai
2. Lihong Li
3. Niao He
4. Mengdi Wang
5. Le Song
6. Ofir Nachum
7. Yichen Chen
8. Albert Eaton Shaw

In Management Science and Operations Research

1. Bo Dai
2. Lihong Li
3. Niao He
4. Mengdi Wang
5. Ofir Nachum
6. Yichen Chen
7. Ziyang Tang
8. Le Song

Citations in the corpus

• Boosting the Actor with Dual Critic (2017, methodology): “…duality have been utilized for (approximate) planning problem (de Farias and Roy, 2004; Wang et al., 2008; Pazis and Parr, 2011; O’Donoghue et al., 2011; Malek et al., 2014; Cogill, 2015), in which the transition probability of the MDP is known and the value function or policy are in tabular form.”
• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, methodology): “Approximate linear programming approaches have been developed for solving the large-scale MDP on a low-dimensional subspace, started with de Farias and Van Roy (2003) and followed by Veatch (2013); Abbasi-Yadkori et al. (2014). Our algorithm and analysis is closely related to the class of stochastic”
• Efficient Sequential Decision Making (2017, result): “This work is an extension of the previous published paper [35].”
• Scalable Bilinear π Learning Using State and Action Features (2018, background): “An exception is Abbasi-Yadkori et al. (2014), who reduces the ALP to stochastic convex optimization.”
• An online primal-dual method for discounted Markov decision processes (2016, background): “Approximate linear programming has been studied for approximating large-scale MDP on a low-dimensional subspace, started with [11] and followed by [1], [23].”