An analysis of reinforcement learning with function approximation

By Francisco S. Melo, Sean P. Meyn, M. Isabel Ribeiro. 2008

288 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Information Systems

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 Computational Theory and Mathematics

In Management Information Systems

Citations in the corpus

Smoothed Dual Embedding Control (2017, methodology): “in the literature for a few rather special cases, as reviewed in the introduction (Boyan & Moore, 1995; Gordon, 1995; Tsitsiklis & Van Roy, 1997; Ormoneit & Sen, 2002; Antos et al., 2008; Melo et al., 2008). Of particular interest is the Greedy-GQ algorithm (Maei et al., 2010), who uses ”
Towards Characterizing Divergence in Deep Q-Learning (2019, background): “Previously, Melo et al. (2008) proved sufﬁcient conditions for the convergence of Q -learning with linear function ap-proximators.”
Dynamic policy programming (2010, background): “Also, there are some studies in the literature concerning the asymptotic convergence of Q-learning in the presence of function approximation (Melo et al., 2008; Szepesvári and Smart, 2004).”
A survey and critique of multiagent deep reinforcement learning (2018, background): “Additionally, convergence results for reinforcement learning using function approximation are still scarce [21,92,207,217,330]; in general, stronger convergence guarantees are available for policy-gradient methods [316] than for value-based methods [315].”
Multi-agent Reinforcement Learning: An Overview (2010, methodology): “Approximate Q-learning is provably convergent if a linearly parameterized approximator is employed, and under the restrictive condition that the agent’s policy is kept ﬁxed while learning [76].”
State of the Art Control of Atari Games Using Shallow Reinforcement Learning (2015, methodology): “Theoretical results suggest that, as an on-policy method, Sarsa(λ) may be more stable in the linear function approximation case than off-policy methods such as Q-learning, which are known to risk divergence [1, 10, 18].”
Experience Replay for Real-Time Reinforcement Learning Control (2012, background): “it does converge (under mild assumptions on the approximator), if the policy used to choose actions is fixed [20], [34].”
Thompson Sampling for Learning Parameterized Markov Decision Processes (2014, background): “In particular, studying the regret of Thompson Sampling for MDPs with linear function approximation (Melo et al., 2008) would be of interest.”
Reinforcement learning in robotic applications: a comprehensive survey (2021, background): “However, in some articles(Melo et al. 2008), authors provide the guarantee of convergence if trajectories are sampled according to on-policy distribution for some parameters function approximators.”
Online Transfer Learning in Reinforcement Learning Domains (2015, methodology): “The convergence of Q-learning and Sarsa with linear approximation in standard setting has been proved Melo et al. (2008), provided the relevant assumptions hold.”
A unifying framework for computational reinforcement learning theory (2009, background): “fact that the Bellman operator when combined with special function approximators is a contraction [Tsitsiklis and Van Roy 1997; Szepesvári and Smart 2004; Melo and Ribeiro 2007; Melo et al. 2008]; see §3.”
Q-learning with Nearest Neighbors (2018, methodology): “For such problems, existing algorithms typically make use of a parametric function approximation method, such as a linear approximation [27], to learn a compact representation of the action-value function.”
Scalable Bilinear π Learning Using State and Action Features (2018, methodology): “Linear basis functions have been used for both policy evaluation and optimization (Tsitsiklis & Van Roy, 1997; Nedić & Bertsekas, 2003; Lagoudakis & Parr, 2003; Melo et al., 2008; Sutton et al., 2009).”
Algorithms for Reinforcement Learning (2010, background): “The only known convergence result is due to Melo et al. (2008) who prove convergence under rather restrictive conditions on the sample distribution.”
Toward Off-Policy Learning Control with Function Approximation (2010, unknown): “Previous theoretical attempts to construct incremental methods with the above properties include that of (Szepesvári & Smart, 2004) and (Melo et al., 2008), which also discuss relevant prior literature.”
Preventing undesirable behavior of intelligent machines (2019, background): “conventional control algorithms are well understood, most RL algorithms have only asymptotic convergence guarantees [192] and in practice are sensitive to the setting of hyperparameters like step sizes, exploration rates, trace decay rates, policy representations, and value function representations ”
Cooperation and communication in multiagent deep reinforcement learning (2016, background): “Instead of neural networks, many reinforcement learning practitioners chose to use linear function approximation (LFA), which yielded more traction for theoretical analysis of convergence properties (Tsitsiklis and Roy, 1997; Melo and Ribeiro, 2007; Melo et al., 2008).”