Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms

By Satinder Singh, Tommi S. Jaakkola, Michael L. Littman, Csaba Szepesvari. 2000

754 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Control and Systems Engineering, Industrial and Manufacturing Engineering, 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 Artificial Intelligence

In Control and Systems Engineering

In Industrial and Manufacturing Engineering

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

Addressing Function Approximation Error in Actor-Critic Methods (2018, background): “We introduce a regularization strategy for deep value learning, target policy smoothing, which mimics the learning update from SARSA (Sutton & Barto, 1998).”
Safe and Efficient Off-Policy Reinforcement Learning (2016, methodology): “To the best of our knowledge, this is the ﬁrst online return-based off-policy control algorithm which does not require the GLIE (Greedy in the Limit with Inﬁnite Exploration) assumption (Singh et al., 2000).”
RUDDER: Return Decomposition for Delayed Rewards (2018, background): “y off-policy immediate reward estimation via Eq. (A84). RUDDER learning can be based on policies like “greedy in the limit with inﬁnite exploration” (GLIE) or “restricted rank-based randomized” (RRR) [118]. GLIE policies change toward greediness with respect to the Q-values during learning. Variant ”
Off-Policy Deep Reinforcement Learning without Exploration (2018, background): “Sketch of the Proof of Convergence of Q-Learning The proof of convergence of Q-learning relies large on the following lemma (Singh et al., 2000): Lemma 2.”
A Multi-Agent Framework for Packet Routing in Wireless Sensor Networks (2015, background): “As argued in [39], stochastic policies can work better than deterministic policies in partially observable environments (such as packet routing in WSNs, where each sensor has only partial information about the entire WSN).”
Mean Field Multi-Agent Reinforcement Learning (2018, methodology): “On the other hand, On-policy methods need to comply with the GLIE assumption (Assumption 2 in Sec 3.3) so as to converge properly to the optimal value (Singh et al., 2000), which is in the end a greedy policy as off-policy methods.”
Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems (2012, background): “The balance between exploration and exploitation is crucial for the efﬁciency of single-agent RL algorithms (Sutton & Barto, 1998; Singh, Jaakkola, Littman, & Szepesvari, 2000).”
Parallel reinforcement learning with linear function approximation (2007, positive): “If the agent’s control policy tends towards greedy choices over time, the Q(s, a) estimates will converge to the optimal value function Q∗(s, a) [4].”
Optimistic Bayesian Sampling in Contextual-Bandit Problems (2012, background): “These considerations result in the consideration of GLIE (greedy in the limit with infinite exploration ) policies, for which action selection is greedy in the limit and also guarantees infinite exploration (Singh et al., 2000).”
A Multi-objective Deep Reinforcement Learning Approach for Stock Index Future’s Intraday Trading (2017, methodology): “These value function methods, such as TD-learning [4], Q-learning [13] and Sarsa [14], are often used to solve discrete space optimization problems.”
Reinforcement learning for control: Performance, stability, and deep approximators (2018, methodology): “In order to converge to Q∗, SARSA requires the same conditions as Q-learning, and in addition that the exploratory policy being followed asymptotically becomes greedy, for instance by letting ε or τ go to 0 in ε-greedy or softmax (Singh et al., 2000).”
Dynamic Safe Interruptibility for Decentralized Multi-Agent Reinforcement Learning (2017, background): “We fill focus on -greedy policies that are greedy in the limit [19], that corresponds to t → 0 when t → ∞ because in the limit, the optimal policy should always be played.”
Reinforcement Learning to Play an Optimal Nash Equilibrium in Team Markov Games (2002, background): “If the learning policy has the “Greedy in the Limit with Infinite Exploration” (GLIE) property, then will converge to (with either a model-based or model-free approach) and the agent will converge in behavior to an optimal policy [14].”