An upper bound on the loss from approximate optimal-value functions

By Satinder Singh, Richard C. Yee. 1994

How researchers see this paper

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

1. Sergey Levine
2. Ofir Nachum
3. Nan Jiang
4. Lihong Li
5. Bo Dai
6. Yoshua Bengio
7. Alekh Agarwal
8. Pieter Abbeel

Citations in the corpus

• Modelling transition dynamics in MDPs with RKHS embeddings (2012, background): “(Singh & Yee, 1994)[Corollary 2] For any action-value function Q : X × A → R , the greedy policy π We are interested in the case where P is unknown but a sample S := { ( x i , a i , x ′ i ) } mi =1 is provided, drawn i.i.d. from a distribution P such that P ( X ′ i = x ′ i | X i = x i , A i = a i )…”
• Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “The more coarse-grained version w.r.t. ℓ ∞ norm has been proved by Singh & Yee (1994).”
• Contextual Decision Processes with low Bellman rank are PAC-Learnable (2016, neutral): “The structure of this lemma is similar to many existing results in RL that upper-bound the loss of following an approximate value function greedily using the function’s Bellman errors (e.g., Singh and Yee [1994]).”
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison (2020, methodology): “One typical way this occurs in AVI analyses is through the use of (some fine-grained variants of) the following result from Singh and Yee [1994], that the performance loss of a policy greedy w.r.t. some Q is bounded by and translating (cid:107) Q − Q (cid:63) (cid:107) to the quantities that the…”
• Sample-Optimal Parametric Q-Learning Using Linearly Additive Features (2019, background): “When each φ(s, a) ∈ RK and ψk ∈ RS is a probability density function, the linear transition model reduces to a soft state aggregation model Singh et al. [1995], Duan et al.”
• Knows what it knows: a framework for self-aware learning (2008, methodology): “We first provide a version of the simulation lemma (Lemma 9), an inequality of Singh and Yee (1994) (Lemma 10), and then verify the three conditions in Theorem 4 in Lemmas 11– 13 to show KWIK-Rmax is PAC-MDP.”
• 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).”
• Tight Performance Bounds for Approximate Modified Policy Iteration with Non-Stationary Policies (2013, background): “In the specific case corresponding to VI (m = 0) and PI (m =∞), this bound matches performance guarantees that have been known for a long time (Singh and Yee, 1994; Bertsekas and Tsitsiklis, 1996).”
• Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems (2006, background): “Corollary 15 [ Singh and Yee (1994) where ˜ π = Greedy ( ˜ Q ) .”
• Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, background): “Results in this setting include Kearns and Singh [1999], Kakade [2003], Singh and Yee [1994], Azar et al. [2013], Sidford et al. [2018b,a], Agarwal et al. [2019].”
• Abstraction Selection in Model-based Reinforcement Learning (2015, unknown): “Our goal is to choose an abstraction h from a candidate set H so as to minimize the loss of the optimal policy for MhD: Loss(h,D) = ∥∥∥∥V ∗M − V π∗MhDM ∥∥∥∥ ∞ .”
• Algorithms for Reinforcement Learning (2010, unknown): “Then the value of policy π can be lower bounded as follows (e.g., Singh and Yee, 1994, Corollary 2): V π(x) ≥ V ∗(x)− 2 1− γ ‖Q−Q∗‖∞, x ∈ X .”
• Reinforcement Learning: Theory and Algorithms (2019, unknown): “[Singh and Yee [1994]] For any vector Q ∈ R|S||A|, V πQ ≥ V ? − 2‖Q−Q ‖∞ 1− γ 1.”
• 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.”