Performance Bounds in Lp-norm for Approximate Value Iteration

By R´emi Munos. 2007

188 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Control and Systems Engineering

How researchers see this paper

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

In Artificial Intelligence

In Control and Systems Engineering

Citations in the corpus

Information-Theoretic Considerations in Batch Reinforcement Learning (2019, methodology): “To this end, Munos (2007) has provided several carefully constructed tabular examples, demonstrating that C does not always scale badly.”
Approximate Policy Iteration Schemes: A Comparison (2014, background): “As a matter of fact, several other dynamic programming algorithms, namely AVI (Munos, 2007), λ PI (Scherrer, 2013), AMPI (Scherrer et al., 2012), come with guarantees involv-7 ing the worst constant C (2 , 1 , 0) , which suggests that they should not be competitive with the best algorithms we have d”
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).”
Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Error (2022, background): “…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; Farahmand et al., 2010).”
Non-delusional Q-learning and value-iteration (2018, background): “Unfortunately, the bounds on induced policy quality using the BE approximation are quite loose, typically 2||BE||∞/(1 − γ) (see [6], bounds with `p norm are similar [20]).”
Action-Gap Phenomenon in Reinforcement Learning (2011, methodology): “1 of Munos [24], one may derive Q∗ − Q̂k+1 = T ∗ Q∗ − T ∗ Q̂k + T π∗Q̂k − T Q̂k + εk ≤ γP ∗ (Q∗ − Q̂k) + εk”
Iterative Value-Aware Model Learning (2018, methodology): “…average concentrability coefﬁcient as The deﬁnition of ¯ C ( ρ, ν ) is similar to the second order discounted future state distribution concentration coefﬁcient of Munos [2007], with the main difference being that it is deﬁned for the expectation of the R-N derivative instead of its supremum.”
Is the Bellman residual a bad proxy? (2016, background): “with the policy πvθ being greedy with respect to vθ [17, 19].”
Regularization in reinforcement learning (2011, unknown): “Similarly for AVI, if the approximation errors are uniformly bounded, that is ‖T Vk − Vk+1‖∞ ≤ ε, we have [Munos, 2007]”
The Importance of Pessimism in Fixed-Dataset Policy Optimization (2020, background): “In that seing, the literature contains ne-grained results on the accumulation of local errors [26].”
A Geometric Perspective on Optimal Representations for Reinforcement Learning (2019, result): “tic norm bounds given by Munos (2003), in whose work the constant is made explicit. We emphasize that the result is illustrative; our approach should enable similar guarantees in other contexts (e.g. Munos, 2007; Petrik and Zilberstein, 2011). 3.1 The Structure of Adversarial Value Functions The RLP”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, background): “concentrability coefficient which assumes that the ratio of the state-action occupancy density induced by any policy and the data distribution is bounded uniformly over all states and actions [24]–[27].”
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.”
Approximate modified policy iteration and its application to the game of Tetris (2015, methodology): “(22) Such a bound is a generalization of the bounds for AVI (m = 1 and = 0) and API (m = ∞) in Bertsekas and Tsitsiklis (1996).”
Boosted Bellman Residual Minimization Handling Expert Demonstrations (2014, background): “where C ∈ R∗ is a constant depending notably on the MDP (for details see the work of [16]).”