Finite-sample analysis of least-squares policy iteration

By Alessandro Lazaric, Mohammad Ghavamzadeh, R´emi Munos. 2012

133 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.

Citations in the corpus

GenDICE: Generalized Offline Estimation of Stationary Values (2020, methodology): “However, as discussed in the literature (Antos et al., 2008; Lazaric et al., 2012; Dai et al., 2018; Nachum et al., 2019), using the blocking technique of Yu (1994), the statistical error provided here can be generalized to β-mixing samples in a single sample path.”
DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections (2019, methodology): “However, by exploiting blocking technique in Proposition 15 of [53], following [2, 23, 9], all the sample complexity we provided can be easily generalized for single β-mixing sample path, i.”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “…appeared in or been implicitly hinted by prior work (especially Szepesv´ari & Munos, 2005; Antos et al., 2008), and we include them because (1) the discussions in the rest of the paper are largely based as its guarantees often rely on similar but more complicated assumptions (Lazaric et al., 2012).”
Batch Mode Reinforcement Learning based on the Synthesis of Artificial Trajectories (2012, background): “Several papers have proposed some theoretical works related to least-squares TD-based algorithms, such as for example Nedi ´ c and Bertsekas (2003) and Lazaric et al. (2010a, 2010b).”
Batch Policy Learning under Constraints (2019, methodology): “…F, when Tg /∈ F, a notion of distance, known as inherent Bellman error was first proposed by (Munos, 2003) and used in the analysis of related ADP algorithms (Munos & Szepesvári, 2008; Munos, 2007; Antos et al., 2008a;b; Lazaric et al., 2010; 2012; Lazaric & Restelli, 2011; Maillard et al., 2010).”
Finite-Sample Analysis of Proximal Gradient TD Algorithms (2015, methodology): “Lazaric et al. [2010b] proposed a LSTD analysis in learner spaces and obtained a tighter bound of O ( d log d nν ) and later used it to derive a bound for the least-squares policy iteration (LSPI) algorithm [Lazaric et al. , 2012].”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, methodology): “…analyses rely on the so-called concentrability coeﬃcients to correct the mismatch between training and test distributions [Farahmand et al., 2010, Lazaric et al., 2012], implicitly assuming that an exploration distribution is given, hence these results do not address the exploration issue which…”
A Kernel Loss for Solving the Bellman Equation (2019, background): “nd by various algorithms (e.g., Sutton, 1988; Boyan, 1999; Sutton et al., 2009; Dann et al., 2014), and its theoretical properties have been extensively studied (e.g., Tsitsiklis & Van Roy, 1997; Lazaric et al., 2012). Corollary 3.5. When using a linear kernel of form k(s;s) = ˚(s)T˚(s), minimiz”
Bellman-consistent Pessimism for Offline Reinforcement Learning (2021, background): “The on-support part matches the n rate (fast rate error bound) of API or AVI analysis (e.g., [Pires and Szepesvári, 2012; Lazaric et al., 2012; Chen and Jiang, 2019]).”
On the Use of Non-Stationary Policies for Stationary Infinite-Horizon Markov Decision Processes (2012, background): “Interestingly, this very constant 2γ (1−γ)2 appears in many works analyzing AVI algorithms [25, 11, 27, 12, 13, 23, 7, 6, 20, 21, 22, 9], API algorithms [15, 19, 16, 1, 8, 18, 5, 17, 10, 3, 9, 2] and in one of their generalization [26], suggesting that it cannot be improved.”
Provably Good Batch Reinforcement Learning Without Great Exploration (2020, methodology): “Our results match the fast rate error bound of API/AVI [7, 32, 5, 22] in their dependence on n.”
Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize (2015, background): “Finally, besides asymptotic behavior of the algorithms, their finite-time or finite-sample properties (such as those considered by [31, 2, 20, 21]), and their large deviations properties are also worth studying.”
A Theoretical Analysis of Deep Q-Learning (2019, background): “See Bradtke and Barto (1996); Boyan (2002); Lagoudakis and Parr (2003); Lazaric et al. (2016); Farahmand et al. (2010); Lazaric et al. (2012); Tagorti and Scherrer (2015) and the references therein for results of the least-squares policy iteration (LSPI) and Bellman residue minimization (BRM)…”
Approximate modified policy iteration and its application to the game of Tetris (2015, background): “On the other hand, approximate PI (API) first finds an approximation of the value of the current policy and then generates the next policy as greedy w.r.t. this approximation (Bertsekas and Tsitsiklis, 1996; Munos, 2003; Lagoudakis and Parr, 2003a; Lazaric et al., 2010b, 2012).”
Regularization in reinforcement learning (2011, result): “Their simplified upper bound for ‖Q−QK‖1,ρ is C 1/2 ρ,ν √ VF log(n) + ln(K/δ)n −1/4, in which VF is the “effective” dimension of F and is defined based on the pseudo-dimension of sub-graphs of F and the so-called “VC-crossing dimension” of F ; and Cρ,ν is a concentrability coefficient and plays a si”
Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL (2020, methodology): “When the action value function of all policies can be linearly represented Munos (2003); Lazaric et al. (2012); Lattimore et al. (2020); Agarwal et al. (2020c) provide algorithms to learn a good policy using a simulator, and online using stronger conditions (Agarwal et al., 2020a); all these…”