Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning

By Yichen Chen, Mengdi Wang. 2016

68 citations recorded by the source corpus.

We study the online estimation of the optimal policy of a Markov decision process (MDP). We propose a class of Stochastic Primal-Dual (SPD) methods which exploit the inherent minimax duality of Bellman equations. The SPD methods update a few coordinates of the value and policy estimates as a new state transition is observed. These methods use small storage and has low computational complexity per iteration. The SPD methods find an absolute-$\epsilon$-optimal policy, with high probability, using $\mathcal{O}\left(\frac{|\mathcal{S}|^4 |\mathcal{A}|^2\sigma^2 }{(1-\gamma)^6\epsilon^2} \right)$ iterations/samples for the infinite-horizon discounted-reward MDP and $\mathcal{O}\left(\frac{|\mathcal{S}|^4 |\mathcal{A}|^2H^6\sigma^2 }{\epsilon^2} \right)$ for the finite-horizon MDP.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Optimization & Training, Statistical Learning Theory

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

In Management Science and Operations Research

In Reinforcement Learning

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, background): “Lee and He (2018) extend a line of work applying to convex optimization techniques to policy optimization (Chen and Wang, 2016; Wang and Chen, 2016; Dai et al., 2017a,b) to the off-policy setting.”
Reinforcement Learning via Fenchel-Rockafellar Duality (2020, methodology): “Depending on the specific regularization employed, deriving the optimal policy from V ∗, K∗ may be difficult in 7The Lagrangian of (72) or (68) may also be used to derive several existing tabular (Chen and Wang, 2016) and on-policy algorithms (Wang, 2017; Dai et al.”
AlgaeDICE: Policy Gradient from Arbitrary Experience (2019, background): “Other works (Chen and Wang, 2016; Wang, 2017; Dai et al., 2018b; Chen et al., 2018) consider the (augmented) Lagrangian of the LP characterization of Bellman optimality for the optimal V -function, which is slightly diﬀerent from the LP characterization with respect to the optimal Q -function we…”
Stochastic Primal-Dual Q-Learning (2018, neutral): “…for any stochastic policy µ s ∈ ∆ |A| , s ∈ S , R µ ( s ) , s ∈ S , is deﬁned as It is well-known (Bertsekas and Tsitsiklis, 1996; Puterman, 2014; Chen and Wang, 2016) that the optimal cost vector, V ∗ ∈ R |S| , can be obtained by solving the linear programming problem (LP) min where η ∈ R |S|…”
Boosting the Actor with Dual Critic (2017, methodology): “For example, for an MDP with ﬁnite state and action spaces, the one-step saddle-point problem (6) with tabular parametrization is convex-concave, and ﬁnite-sample convergence rates can be established; see e.g., Chen and Wang (2016) and Wang (2017).”
Smoothed Dual Embedding Control (2017, background): “Several recent works (Chen and Wang, 2016; Wang, 2017) have also considered saddle point formulations of Bellman equations, but these formulations are fundamentally different from ours, even from its origin.”
Applications of reinforcement learning in energy systems (2021, methodology): “Furthermore, by exploiting the minimax duality of Bellman equations, a class of stochastic primal-dual (SPD) methods that is computational and sample-efficient has been proposed for RL [186].”
Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time (2017, background): “The work [29] and its journal version [8] considered a basic stochastic primal-dual iteration that uses Euclidean projection and uniform sampling of state-action pairs to solve DMDP and established a sample complexity upper bound O(|S|4.”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, unknown): “In reinforcement learning, solving Bellman equations can also be reformulated as minimax optimization problems [Chen and Wang, 2016, Dai et al., 2017, 2018].”
Stochastic Primal-Dual Q-Learning Algorithm For Discounted MDPs (2019, methodology): “In particular, [15] considers a linear programming form of the Bellman equation and introduces a stochastic primaldual (SPD) algorithm to solve the min-max problem of”
Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD (2018, methodology): “On the other hand, if we follow the analysis of the stochastic primal-dual algorithm in [17], we can prove that under certain conditions the iterations of Algorithm 1 converge to the the stationary points in Proposition 3.”
Scalable Bilinear π Learning Using State and Action Features (2018, methodology): “Reinforcement learning lies at the intersection between control, machine learning, and stochastic processes (Bertsekas and Tsitsiklis, 1996; Sutton and Barto, 1998).”
Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems (2017, background): “For the discounted MDP, the work [26] proposed a basic stochastic primal-dual iteration without explicit complexity analysis and later [6] ).”
Harnessing Inﬁnite-Horizon Off-Policy Evaluation: Double Robustness via Duality (2019, methodology): “Primal-Dual Value Learning Primal-dual optimization techniques have been widely used for off-policy value function learning and policy optimization (Liu et al., 2015; Chen & Wang, 2016; Dai et al., 2017a,b; Feng et al., 2019).”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “Besides the value- and policy-based methods, there also exist RL algorithms based on the linear program formulation of an MDP; see recent efforts in [80, 81].”