On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming

By D. Farias, Benjamin Van Roy. 2004

434 citations recorded by the source corpus.

In the linear programming approach to approximate dynamic programming, one tries to solve a certain linear program--the ALP--that has a relatively small numberK of variables but an intractable numberM of constraints. In this paper, we study a scheme that samples and imposes a subset ofm <

Subfields: Artificial Intelligence, Computer Networks and Communications

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. Sergey Levine
2. Bernhard Schölkopf
3. Le Song
4. Bo Dai
5. Arthur Gretton
6. Alex Smola
7. Jan Peters
8. Lihong Li

In Computer Networks and Communications

1. Marco Claudio Campi
2. Lihong Li
3. Simone Garatti
4. Carlos Guestrin
5. Bo Dai
6. Arkadi Nemirovski
7. Ronald E. Parr
8. Le Song

Citations in the corpus

• Boosting the Actor with Dual Critic (2017, methodology): “The linear programming representation of Bellman optimality equation and its 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…”
• Efficient Solution Algorithms for Factored MDPs (2003, background): “Recent work by de Farias and Van Roy (2001a, 2001b) has started to address these concerns with new error bounds and constraint sampling methods.”
• Convex Approximations of Chance Constrained Programs (2006, positive): “To some extent this question was resolved in recent papers of Calafiore and Campi [6] [7] and de Farias and Van Roy [10].”
• Self-regularity - a new paradigm for primal-dual interior-point algorithms (2002, background): “Other interesting and important results on scenario approximations of chance constrained problems can be found in [44, 66] (the latter paper addresses the case of an ambiguous chance constraint).”
• Robust Optimization (2021, background): “chance constrained problems can be found in [35, 50] (the latter paper addresses the case of an ambiguous chance constraint).”
• Ambiguous chance constrained problems and robust optimization (2006, methodology): “Recently, Calaore and Campi [10, 11] and de Farias and Van Roy [ 14 ] independently proposed tractable approximations to (3) based on constraint sampling and statistical learning techniques.”