Error Bounds for Approximate Value Iteration

By R´emi Munos. 2005

165 citations recorded by the source corpus.

Subfields: 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 Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction (2020, background): “While a number of prior works have provided a theoretical examination of various approximation dynamic programming (ADP) methods – which encompasses Q-learning and actor-critic algorithms – prior work has not extensively studied the relationship between the data distribution induced by the latest va”
Keep Doing What Worked: Behavioral Modelling Priors for Offline Reinforcement Learning (2020, background): “…papers have theoretically analyzed the accumulation of bootstrapping errors in approximate dynamic programming (Bertsekas & Tsitsiklis, 1996; Munos, 2005) and approximate policy iteration (Farahmand et al., 2010; Scherrer et al., 2015); for the latter of which there exist well known…”
Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction (2019, methodology): “A similar bound also holds true for value iteration with the T Π operator which can be analysed on similar lines as the above proof and Munos [29].”
Diagnosing Bottlenecks in Deep Q-learning Algorithms (2019, background): “For similar results concerning µ -weighted 2 norms, see (Munos, 2005).”
On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift (2019, methodology): “The existing literature largely consists of two lines of provable guarantees that attempt to mitigate the explicit l∞ error conditions of approximate dynamic programming: those methods which utilize a problem dependent parameter (the concentrability coefficient [Munos, 2005]) to provide”
Provably Good Batch Reinforcement Learning Without Great Exploration (2020, methodology): “Since both AVI and API suffer from bootstrapping errors in less visited regions of the MDP even in the tabular setting, FQI and FPI approaches have the same drawback.”
Safe Policy Iteration (2013, background): “Most API studies and algorithms focus on reducing the approximation error in the policy evaluation step (Lagoudakis & Parr, 2003; Munos, 2005; Lazaric et al., 2010; Gabillon et al., 2011), and then perform policy improvement by taking the related greedy policy.”
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes (2019, methodology): “In particular, the results in [Munos, 2005, Antos et al., 2008] (and other results using concentrability) provide optimal policies in the case when γ = 0.”
Proto-value Functions: A Laplacian Framework for Learning Representation and Control in Markov Decision Processes (2007, methodology): “There continues to be work on developing more useful weighted least-square bounds, although these currently assume the policy is exactly representable (Munos, 2003, 2005).”
Dynamic Policy Programming with Function Approximation (2011, methodology): “Following Munos (2005), Lp-norm bounds for approximate DPP can be established by providing a bound on the performance loss of each component of value function under the policy induced by DPP.”
Finite-Time Bounds for Fitted Value Iteration (2008, background): “Preliminary versions of the results presented here were published in Szepesvári and Munos (2005).”
Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning? (2019, background): “While classical approximate dynamic programming results typically require ∞ -bounded errors, the notion of concentrability (originally due to (Munos, 2005)) permits sharper bounds in terms of average-case function approximation error, provided that the concentrability coefﬁcient is bounded (e.g.…”
Finite time bounds for sampling based fitted value iteration (2005, background): “Unlike Munos (2003) and later (Munos, 2005), we do not assume that an exact model of the environment is available, but we consider in detail the influence that finite random samples can have on the final error.”
DDPG++: Striving for Simplicity in Continuous-control Off-Policy Reinforcement Learning (2020, background): “This is a fundamental open problem in reinforcement learning [25–28] and solutions to it are necessary to enable deployment of deep RL techniques in robotics.”
Scaling Up Approximate Value Iteration with Options: Better Policies with Fewer Iterations (2014, background): “A key assumption needed for their analysis is the notion of discounted-average concentrability of future state distributions.”
Approximate Value Iteration with Temporally Extended Actions (2015, background): “[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 . . .”
Point-Based POMDP Algorithms: Improved Analysis and Implementation (2005, methodology): “Its use of weighted max-norm machinery in value iteration is closely related to [Munos, 2004].”