On the role of tracking in stationary environments

By Richard S. Sutton, Anna Koop, David Silver. 2007

112 citations recorded by the source corpus.

It is often thought that learning algorithms that track the best solution, as opposed to converging to it, are important only on nonstationary problems. We present three results suggesting that this is not so. First we illustrate in a simple concrete example, the Black and White problem, that tracking can perform better than any converging algorithm on a stationary problem. Second, we show the same point on a larger, more realistic problem, an application of temporal difference learning to computer Go. Our third result suggests that tracking in stationary problems could be important for metalearning research (e.g., learning to learn, feature selection, transfer). We apply a metalearning algorithm for step-size adaptation, IDBD (Sutton, 1992a), to the Black and White problem, showing that meta-learning has a dramatic long-term effect on performance whereas, on an analogous converging problem, meta-learning has only a small second-order effect. This small result suggests a way of eventually overcoming a major obstacle to meta-learning research: the lack of an independent methodology for task selection.

Subfields: Artificial Intelligence

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

Citations in the corpus

Reinforcement learning in robotics: A survey (2013, background): “As the dynamics of a robot can change due to many external factors ranging from temperature to wear, the learning process may never fully converge, i.e. it needs a “tracking solution” (Sutton et al., 2007).”
Continuous Adaptation via Meta-Learning in Nonstationary and Competitive Environments (2017, methodology): “Besides our proposed method for continuous adaptation via meta-learning, we consider three baseline strategies: (i) naive (or no adaptation), (ii) implicit adaptation via RL 2 , and (iii) adaptation via tracking [5] that uses PPO for online updates at execution time.”
Learning to Win by Reading Manuals in a Monte-Carlo Framework (2011, background): “Learning a specialized Q(st, at) for each game state is common and useful in games with complex state spaces and dynamics, where learning a single global function approximation can be particularly difficult (Sutton et al., 2007).”
Lifelong Machine Learning Systems: Beyond Learning Algorithms (2013, background): “In (Sutton, Koop, and Silver 2007), Sutton et al. suggests that learning should continue during an agent's operations since the environment may change making prior learning insufficient .”
RLLib: C++ Library to Predict, Control, and Represent Learnable Knowledge Using On/Off Policy Reinforcement Learning (2015, unknown): “RLLib implements and features: 1) off-policy prediction algorithms: (GTD(λ) and GQ(λ)) [14]; 2) off-policy control algorithms: Greedy-GQ(λ) [14] and (Softmax GQ(λ) and Off-PAC) [5]; 3) on-policy algorithms: (TD(λ), SARSA(λ), Expected SARSA(λ), and Actor-Critic (continuous and discrete actions, disco”
Transfer Learning for Reinforcement Learning Domains: A Survey (2009, background): “First, transfer algorithms may reasonably focus on transfer between a single pair of related tasks,r ther than attempting to account for any future task that an agent could encounter.”
A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity (2017, background): “An analysis of these two approaches in a stationary task found that in certain cases a tracking algorithm obtains better results than one that converges to the optimal policy (Sutton et al., 2007).”
Model-Free reinforcement learning with continuous action in practice (2012, unknown): “An alternative is to use online learning to track environmental changes and adapt to them (e.g., see [1]).”
Dealing with Non-Stationarity in Multi-Agent Deep Reinforcement Learning (2019, methodology): “Before advances in deep RL, approaches like tracking (Sutton et al. , 2007) and context detection (Da Silva et al. , 2006) were proposed to allow quicker adaptation in non-stationary environments.”
Deep Reinforcement Learning amidst Continual Structured Non-Stationarity (2021, background): “On-policy RL algorithms can in principle cope with such non-stationarity (Sutton et al., 2007).”
ELLA: An Efficient Lifelong Learning Algorithm (2013, background): “Lifelong learning has also been explored for reinforcement learning (Ring, 1997; Sutton et al., 2007) and learning by reading (Carlson et al., 2010).”
Continual Backprop: Stochastic Gradient Descent with Persistent Randomness (2021, background): “Non-stationarities can arise due to high complexity (Sutton et al., 2007), partial observability (Khetarpal et al., 2020), other actors (Foerster et al., 2018), or changes in the environment (Thurn, 1998).”
Intrinsically Motivated Reinforcement Learning: An Evolutionary Perspective (2010, background): “[48] make related observations about the limitations of asymptotic optimality.”
Deep Reinforcement Learning amidst Lifelong Non-Stationarity (2020, background): “On-policy RL algorithms can in principle cope with such non-stationarity (Sutton et al., 2007).”
Continual Learning In Environments With Polynomial Mixing Times (2021, background): “Tracking Approaches: It was originally noted by [25] that it could be a better strategy even in stationary environments with temporal coherence to learn to track the best local solution instead of attempting to converge to a globally optimal ﬁxed policy.”
A CCELERATING O NLINE R EINFORCEMENT L EARNING VIA M ODEL -B ASED M ETA -L EARNING (2021, background): “In the real world, humans and animals continually adapt to non-stationary environments that change signiﬁcantly over time due to other agents (Lowe et al., 2017; Foerster et al., 2017), environment complexity (Sutton et al., 2007), or changes in dynamics or goals (Thrun, 1998).”
Transfer Learning in Deep Reinforcement Learning: A Survey (2020, methodology): “The notion of Lifelong Learning is applicable to both traditional machine learning [33] and RL [34], [35], where the later is closely related to the topic of Meta Reinforcement Learning [36].”
Sample-based learning and search with permanent and transient memories (2008, methodology): “Thepotentialfor specialisation means that tracking methods may outperform converging methods, even in stationary domains(Sutton et al., 2007).”