Stable Function Approximation in Dynamic Programming

By Geoffrey J. Gordon. 1995

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

Off-Policy Deep Reinforcement Learning without Exploration (2018, methodology): “While batch reinforcement learning algorithms have been shown to be convergent with non-parametric function approximators such as averagers (Gordon, 1995) and kernel methods (Ormoneit & Sen, 2002), they make no guarantees on the quality of the policy without inﬁnite data.”
Graying the black box: Understanding DQNs (2016, methodology): “Unfortunately, such methods are known to be unstable or even to diverge when used to represent the action-value function (Tsitsiklis & Van Roy, 1997; Gordon, 1995; Riedmiller, 2005).”
D4RL: Datasets for Deep Data-Driven Reinforcement Learning (2020, background): “Moreover, the strongest convergence results in RL require conditions such as on-policy data collection [Bertsekas and Tsitsiklis, 1996], function class restrictions [Gordon, 1995] or restrictions on the MDP family [Agarwal et al., 2019a, Du et al., 2020].”
Smoothed Dual Embedding Control (2017, background): “For example, • for some rather restrictive function classes that have a non-expansion property, such as kernel averaging, most of the finite-state MDP theory continues to apply (Gordon, 1995); • when linear function classes are used to approximate the value function of a fixed policy from on-policy ”
Information-Theoretic Considerations in Batch Reinforcement Learning (2019, background): “Furthermore, additional assumptions are not necessarily made on the value-function class (e.g., that b T F being a contraction (Gordon, 1995; Szepesv´ari & Smart, 2004; Lizotte, 2011; Pires & Szepesv´ari, 2016)), and can instead take the form of requiring another function class to realize other…”
Towards Characterizing Divergence in Deep Q-Learning (2019, methodology): “To make progress toward such a characterization, we give an analysis inspired by Gordon (1995), who studied the behavior of approximate value learning algorithms in value space.”
Increasing the Action Gap: New Operators for Reinforcement Learning (2015, background): “D ( x | z ) = I [ x = z ] , we recover the class of averagers (Gordon 1995; e.g., multilinear interpolation, illustrated in Figure 2) and kernel-based meth-ods (Ormoneit and Sen 2002).”
Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability (2017, methodology): “Practical TD methods instead use function approximators (Gordon, 1995) such as linear combinations of basis functions or neural networks, leveraging inductive bias to execute similar actions in similar states.”
Decentralized Likelihood Quantile Networks for Improving Performance in Deep Multi-Agent Reinforcement Learning (2018, background): “…error for time step t follows distributional bellmen operator: Thus, with τ 1: N , τ 1: N (cid:48) , the loss is given by: Distributional learning have long been considered a promising approach in approximate reinforcement learning due to reduced chattering (Gordon, 1995; Kakade & Langford, 2002).”
A Distributional Perspective on Reinforcement Learning (2017, neutral): “When combined with function approximation, this instability may prevent the policy from converging, what Gordon (1995) called chattering .”
Benchmarking Batch Deep Reinforcement Learning Algorithms (2019, background): “However, these traditional algorithms only come with convergence guarantees for non-parametric function approximation [Gordon, 1995, Ormoneit and Sen, 2002], have no guarantees on the quality of the learned policy, and scale poorly to high dimensional tasks.”
Batch Mode Reinforcement Learning based on the Synthesis of Artificial Trajectories (2012, background): “More generally, we believe that the notion of artiﬁcial trajectory could also be used to characterize other batch mode RL algorithms that rely on other kinds of “averaging” schemes (Gordon 1995).”
Efficient Solution Algorithms for Factored MDPs (2003, methodology): “Tsitsiklis and Van Roy (1996a) and, independently, Gordon (1995) popularized the analysis of approximate MDP methods via the contraction properties of the dynamic programming operator and function approximator.”
Should one compute the Temporal Difference fix point or minimize the Bellman Residual? The unified oblique projection view (2010, positive): “…when ξ is the stationary distribution of P ) and in this case we know from Bertsekas & Tsitsiklis (1996); Tsitsiklis & Van Roy (1997) that ‖v − v̂TD‖ξ ≤ 1 √ 1− γ2 ‖v − v̂best‖ξ. (3) Another notable such exception is when ‖Π‖max = 1, as in the so-called “averager” approximation (Gordon, 1995).”
A Kernel Loss for Solving the Bellman Equation (2019, methodology): “…such as neural networks is used to represent the value function in large-scale problems, the critical property of contraction is generally lost (e.g., Boyan & Moore, 1995; Baird, 1995; Tsitsiklis & Van Roy, 1997), except in rather restricted cases (e.g., Gordon, 1995; Tsitsiklis & Van Roy, 1997).”
On Oracle-Efficient PAC RL with Rich Observations (2018, methodology): “First, we show that methods that compute optimal values iteratively in the style of fitted value iteration [38] need additional assumptions on G and Π besides realizability (Theorem 45).”
Is the Bellman residual a bad proxy? (2016, methodology): “Some classical ADP approaches actually minimize a projected Bellman residual, (cid:107) Π( T ∗ v θ − v θ ) (cid:107) , where Π is the operator projecting onto the hypothesis space to which v θ belongs: Approximate Value Iteration (AVI) [11, 9] tries to minimize this using a ﬁxed-point approach, v θ ”
A unifying framework for computational reinforcement learning theory (2009, methodology): “The algorithm was originally proposed for non-discounting, minimum-cost problems by McMahan and Gordon [2005], while we use a discount factor and consider reward-maximizing problems.”