Error Bounds for Approximate Policy Iteration

By R´emi Munos. 2003

344 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

D4RL: Datasets for Deep Data-Driven Reinforcement Learning (2020, background): “…those from deterministic expert policies, are particularly problematic for oﬄine RL algorithms and may cause divergence both empirically [Fujimoto et al., 2018, Kumar et al., 2019] and theoretically [Munos, 2003, Farahmand et al., 2010, Kumar et al., 2019, Agarwal et al., 2019a, Du et al., 2020].”
DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction (2020, methodology): “(Munos, 2003) analyze error propagation in approximate policy iteration methods using quadratic norms.”
Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reduction (2019, background): “Errors arising from inadequate sampling, distributional shift, and function approximation have been rigorously studied as “error propagation” in approximate dynamic programming (ADP) [5, 28, 11, 34].”
Learning When-to-Treat Policies (2019, background): “Such results also require a bound on the concentratability coefficient (Munos, 2003), which measures the ratio of the state action distribution of a policy to the state-action distribution under the behavior policy, for any behavior policy (e.”
Off-Policy Deep Reinforcement Learning by Bootstrapping the Covariate Shift (2019, methodology): “) Pn ˇ (s 0js): Further, the series can be bounded by a constant, K ˇ;;nK ˇ;:= d (s) d ˇ(s) ing the 1 Xd ˇ(s) d (s) 1 : The term K ˇ;;nis a concentration coefﬁcient similar to those studied by Munos (2003). Intuitively, it measures the discrepancy in stationary distributions between two states that”
Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis (2015, methodology): “Such an analysis may proceed similarly to that in Munos (2003) for the on-policy case.”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “The original deﬁnition is due to Munos (2003).”
Approximate Policy Iteration Schemes: A Comparison (2014, methodology): “CPI, CPI( α ), API( α ): Conservative steps are addressed by a tedious generalization of the proof for API by Munos (2003).”
Off-policy learning with eligibility traces: a survey (2013, methodology): “As they only address the policy evaluation problem, we compare the algorithms in their ability to perform policy evaluation (no control, no policy optimization); however, they may straightforwardly be used in an approximate policy iteration approach (Bertsekas and Tsitsiklis, 1996; Munos, 2003)).”
Batch Policy Learning under Constraints (2019, methodology): “We use the notion of concentration coefficient for the worst case, proposed by (Munos, 2003), to measure the degree of distribution shift.”
Should one compute the Temporal Difference fix point or minimize the Bellman Residual? The unified oblique projection view (2010, background): “Though several works have compared and considered both methods (Schoknecht, 2002; Lagoudakis & Parr, 2003; Munos, 2003; Yu & Bertsekas, 2008), the following simple fact has, to our knowledge, never been emphasized per se: Proposition 1 The BR is an upper bound of the TD error, and more…”
Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, methodology): “A simple procedure described in Algorithm 2, can guess the value of M on a doubling schedule and handle this situation with no consequences to asymptotic sample complexity.”
The Value Function Polytope in Reinforcement Learning (2019, methodology): “The value function is also a useful tool for the analysis of approximation errors (Bertsekas & Tsitsiklis, 1996; Munos, 2003).”
Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Error (2022, background): “The role of the Bellman error has been considered in depth in the literature, in the context of bounds on the performance of a greedy policy in relation to the norm of the Bellman error (Williams & Baird, 1993; Singh & Yee, 1994; Bertsekas & Tsitsiklis, 1996; Heger, 1996; Munos, 2003; 2007; Farahman”
Action-Gap Phenomenon in Reinforcement Learning (2011, methodology): “To analyze this dependence, we deﬁne a concentrability coefﬁcient and use a change of measure argument similar to the work of Munos [23, 24], Antos et al. [10].”
Programming by Feedback (2014, methodology): “This failure is blamed on the fact that the Q-value is learned using a meansquare error criterion, whereas the LSPI efficiency depends on the L∞ error (see discussion in (Munos, 2003)).”
Performance Bounds for Lambda Policy Iteration and Application to the Game of Tetris (2007, methodology): “approximation erros are uniformly bounded, the diﬀerence between the asymptotic performance of policies πk+1 greedy with respect to vk satisﬁes limsup k→∞ kv∗ −vπkk ∞ ≤ 2γ (1 −γ)2 sup k≥0 kǫkk∞ . (5) Munos (2003, 2007) has recently argued that, since most supervised learning algorithms (such as leas”
A Geometric Perspective on Optimal Representations for Reinforcement Learning (2019, background): “This lets us provide guarantees on the performance of learning procedures such as approximate policy iteration (Munos, 2003).”
Analyzing feature generation for value-function approximation (2007, methodology): “Although we have demonstrated the use of the BEBF approach with unweighted projections and policy improvement in LSPI, this application goes beyond the theoretical analysis, so there is room for further theoretical development, perhaps drawing inspiration from the work of Munos (2003). In the area o”