Finite-Time Bounds for Fitted Value Iteration

By R´emi Munos, Csaba Szepesvari. 2008

604 citations recorded by the source corpus.

Subfields: Statistics and Probability, Reinforcement Learning, 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 Statistics and Probability

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

MOReL : Model-Based Offline Reinforcement Learning (2020, methodology): “A number of algorithms based on MPC [23, 64], search-based planning [65, 25], dynamic programming [49, 26], or policy optimization [27, 51, 66, 67] can be used to approximately realize this.”
DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction (2020, background): “(Munos, 2005; Munos and Szepesvári, 2008; Farahmand et al., 2010; Scherrer et al., 2015; Lesner and Scherrer, 2013; Scherrer, 2014) focused on analysing error induced in Bellman projections, under the assumption of an abstract error model.”
Diagnosing Bottlenecks in Deep Q-learning Algorithms (2019, background): “Munos & Szepesvári (2008); Maillard et al. (2010); Tosatto et al. (2017) provide such PAC-bounds which account for sampling error in the context of Q-learning and value-based methods, and quantify the quality of the final solution in terms of sample complexity.”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, methodology): “…Existing works that analyze error propagation and ﬁnite sample behavior of ADP methods (Munos, 2003; Szepesv´ari & Munos, 2005; Antos et al., 2008; Munos & Szepesv´ari, 2008; Tosatto et al., 2017) have provided us with a decent understanding: To guarantee sample-efﬁcient learning of…”
COMBO: Conservative Offline Model-Based Policy Optimization (2021, methodology): “When given an ofﬂine dataset D , standard approximate dynamic programming (ADP) and actor-critic methods use this criterion to alternate between policy evaluation [40] and policy improvement.”
Batch Mode Reinforcement Learning based on the Synthesis of Artificial Trajectories (2012, background): “More theoretical works related with FQI have also been published (Munos and Szepesvári 2008; Chakraborty et al. 2008).”
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).”
Dynamic policy programming (2010, positive): “…correct (PAC) bounds for SADPP and DPP-RL in the spirit of previous theoretical re-sults available for ﬁtted value iteration and ﬁtted Q -iteration (Munos and Szepesv´ari, 2008; Our main result is in the form of following ﬁnite-iteration performance-loss bound, for all k ≥ 0: Here, Q π k is the…”
Finite-Sample Analysis of Proximal Gradient TD Algorithms (2015, methodology): “…work on ﬁnite-sample analysis in RL has been focused on batch RL (or approximate dynamic programming) algorithms (e.g., Kakade and Langford 2002; Munos and Szepesv´ari 2008; Antos et al. 2008; Lazaric et al. 2010a), especially those that are least squares TD (LSTD)-based (e.g., Lazaric et al.…”
Should one compute the Temporal Difference fix point or minimize the Bellman Residual? The unified oblique projection view (2010, methodology): “In (Munos & Szepesvári, 2008), the authors use an algorithm based on the TD Error and make an assumption on this adequacy term (there called the inherent Bellman error of the approximation space), so that their algorithm can be proved convergent.”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, background): “Another related body of work provides sample complexity bounds for ﬁtted value/policy iteration meth-ods (e.g., [Munos, 2003, Antos et al., 2008, Munos and Szepesv´ari, 2008]).”
Plan Online, Learn Offline: Efficient Learning and Exploration via Model-Based Control (2018, background): “The importance of having a wide and relevant state distribution for RL methods has been pointed out in numerous prior works [10, 43, 44].”
Empirical Study of Off-Policy Policy Evaluation for Reinforcement Learning (2019, background): “• Misspecified but good generalization: Function classes such as neural networks have powerful generalization ability, but may introduce bias and inherent Bellman error5 [38, 9] (see linear vs.”
On Oracle-Efficient PAC RL with Rich Observations (2018, methodology): “Theorem 45 provides concrete motivation for stronger realizability conditions such as Assumption 9, variants of which are also used in prior analysis of FVI-type methods [41].”
Iterative Value-Aware Model Learning (2018, background): “…central to value-based approaches such as the family of (Approximate) Value Iteration [Gordon, 1995, Szepesvári and Smart, 2004, Ernst et al., 2005, Munos and Szepesvári, 2008, Farahmand et al., 2009, Farahmand and Precup, 2012, Mnih et al., 2015, Tosatto et al., 2017, Farahmand et al., 2017b] or…”
Offline Reinforcement Learning with Pseudometric Learning (2021, methodology): “Similarly to fitted value-iteration methods (Bertsekas & Tsitsiklis, 1996; Munos & Szepesvari, 2008), which is the basis for the DQN algorithn (Mnih et al., 2015), we consider the parameters of the image of the operator F̂ to be fixed, and note it F̂(dΦ̄).”
Approximate Value Iteration with Temporally Extended Actions (2015, methodology): “[A1(ν, µ)] [Discounted-Average Concentrability of Future-State Distributions] (Munos, 2005; Munos & Szepesvári, 2008) Given two distributions ν and µ defined over the state space X, m ≥ 1, and m arbitrary policies π 1 , π 2 , . . . , π m , we assume that νP π 1 P π 2 . . .”