Sample-Optimal Parametric Q-Learning Using Linearly Additive Features

By Lin F. Yang, Mengdi Wang. International Conference on Machine Learning, 2019

347 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/12cd30cab8281567f5a1e8e3145641336fbb819c

How researchers see this paper

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

1. Simon Shaolei Du
2. Zhuoran Yang
3. Yu Bai
4. Chi Jin
5. Alekh Agarwal
6. Wen Sun
7. Nan Jiang
8. Jason D. Lee

Citations in the corpus

• Is Pessimism Provably Efficient for Offline RL? (2020, methodology): “(iii) For the linear MDP (Yang and Wang, 2019; Jin et al., 2020), we instantiate PEVI by specifying the penalty function in Section 4.2.”
• Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation (2020, methodology): “Similar to Lemma 14 in (Dani et al., 2008) and Lemma 13 in (Yang & Wang, 2019), we apply Freedman’s inequality to show that when ϑ h, 1 , . . . , ϑ h,N are appropriately chosen, the truncated martingale =1 α ,t n =1 , 2 ,...,N never grows too large.”
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? (2019, background): “Later work gave computationally efficient algorithms for certain special cases (Dann et al., 2018; Du et al., 2019a; Yang & Wang, 2019b; Jin et al., 2019).”
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation (2021, background): “, linear MDPs [20, 10]) has been used in [17], which assumes that P(s′|s, a) = 〈φ(s, a),μ(s′)〉 and rh = 〈φ(s, a),θh〉, μh(·) is a measure and θh is an unknown vector.”
• Provably Efficient Exploration in Policy Optimization (2019, methodology): “sting work on valuebased reinforcement learning (Jaksch et al., 2010; Osband et al., 2014; Osband and Van Roy, 2016; Azar et al., 2017; Dann et al., 2017; Strehl et al., 2006; Jin et al., 2018, 2019; Yang and Wang, 2019a,b), lacks such a notion of robustness. On the other hand, an intriguing questio”
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, methodology): “…and Jamieson, 2019, Efroni et al., 2019, Cai et al., 2019] or the generative model (simulator) setting [Azar et al., 2013, Sidford et al., 2018a,b, Yang and Wang, 2019, Agarwal et al., 2020, Wainwright, 2019, Lattimore and Szepesvari, 2019], both of which assuming interactive access to the…”
• Provably efficient representation selection in Low-rank Markov Decision Processes: from online to offline RL (2021, methodology): “In the low-rank MDP framework [Yang and Wang, 2019, Jin et al., 2020], the transition kernel is assumed to be a bi-linear function of the state-action feature vector and an unknown measure θ h ( s ′ ) of dimension d , i.e., P h ( s ′ | s, a ) = ⟨ ϕ ( s, a ) , θ h ( s ′ ) ⟩ .”
• Recent advances in reinforcement learning in finance (2021, background): “14)) are equivalent under mild conditions [125, 255].”
• Provably Efficient Reinforcement Learning with Linear Function Approximation (2019, background): “Recently, Yang and Wang [49] revisited the setting of linear transitions and rewards [12, 29] (Assumption A), and presented a sample-efficient algorithm assuming the access to a “simulator”.”
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction (2020, methodology): “Additionally, finite-time performance of Q-learning and its variants have been analyzed by [5, 9, 20, 28, 35, 44, 48] in the tabular setting, by [6, 8, 10, 17, 18, 21, 49, 52] in the context of function approximations, and by [36] with nonparametric regression.”
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison (2020, methodology): “In the second claim, which is the more restricted “linear MDP” setting recently studied by e.g., Yang and Wang [2019], we are able to bring |W| down to as low as k + 1 ; it is also interesting to point out that we cannot guarantee w dπQ / µ ∈ sp( W ) , but using the linear structure of Q we can…”
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, background): “Turning to reinforcement learning with function approximation and exploration, a large body of effort focuses on (essentially) linear methods (Yang and Wang, 2019b; Jin et al., 2019; Cai et al., 2019; Modi et al., 2020; Du et al., 2019c; Wang et al., 2019).”
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift (2019, background): “For the realizable case, where all policies have values which are linear in the given features (such as in linear MDP models of (Jin et al., 2019; Yang and Wang, 2019; Jiang et al., 2017)), we have that the approximation error approx is 0.”
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, methodology): “When the probability transition model P cannot be fully embedded using φ, then value function approximation using φ may lead to arbitrarily large Bellman error (Yang & Wang, 2019).”