Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear Running Time

By Mengdi Wang. 2017

32 citations recorded by the source corpus.

How researchers see this paper

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

1. Ofir Nachum
2. Sergey Levine
3. Bo Dai
4. Lihong Li
5. Ilya Kostrikov
6. Dale Schuurmans
7. Mengdi Wang
8. Nan Jiang

Citations in the corpus

• AlgaeDICE: Policy Gradient from Arbitrary Experience (2019, background): “Several recent works (e.g., Chen and Wang, 2016; Wang, 2017; Dai et al., 2018a,b; Chen et al., 2018; Lee and He, 2018) also considered saddle-point formulations for policy improvement, derived from fundamentally different perspectives.”
• Boosting the Actor with Dual Critic (2017, methodology): “For example, for an MDP with finite state and action spaces, the one-step saddle-point problem (6) with tabular parametrization is convex-concave, and finite-sample convergence rates can be established; see e.g., Chen and Wang (2016) and Wang (2017).”
• Scalable Bilinear π Learning Using State and Action Features (2018, methodology): “The proofs of Lemma 1 and 2 are deferred to the appendix.”
• Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems (2017, methodology): “Our proof shares a similar spirit as that of Theorem 1 in [25].”