Context Tree Switching

By Joel Veness, Kee Siong Ng, Marcus Hutter, Michael H. Bowling. 2011

51 citations recorded by the source corpus.

This paper describes the Context Tree Switching technique, a modification of Context Tree Weighting for the prediction of binary, stationary, n-Markov sources. By modifying Context Tree Weighting's recursive weighting scheme, it is possible to mix over a strictly larger class of models without increasing the asymptotic time or space complexity of the original algorithm. We prove that this generalization preserves the desirable theoretical properties of Context Tree Weighting on stationary n-Markov sources, and show empirically that this new technique leads to consistent improvements over Context Tree Weighting as measured on the Calgary Corpus.

Subfields: Artificial Intelligence, Probabilistic & Bayesian Methods, Information Theory, Signal Processing

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

1. Sergey Levine
2. Yoshua Bengio
3. Pieter Abbeel
4. Razvan Pascanu
5. Joelle Pineau
6. Chelsea Finn
7. Ruslan Salakhutdinov
8. Marc G. Bellemare

In Probabilistic & Bayesian Methods

1. Erik Talvitie
2. Marc G. Bellemare
3. Joel Veness
4. Romain Laroche
5. Paul Trichelair
6. R´emi Munos
7. Tom Everitt
8. Razvan Pascanu

In Information Theory

1. Marc G. Bellemare
2. Joel Veness
3. Erik Talvitie
4. Tor Lattimore
5. Romain Laroche
6. Paul Trichelair
7. Guillaume Desjardins
8. Tom Everitt

In Signal Processing

1. Marc G. Bellemare
2. Erik Talvitie
3. R´emi Munos
4. Georg Ostrovski
5. Romain Laroche
6. Paul Trichelair
7. Joel Veness
8. Razvan Pascanu

Citations in the corpus

• Overcoming catastrophic forgetting in neural networks (2016, methodology): “Instead we use the result from [Veness et al., 2012] where it is shown that a time decaying switch rate α = 1 /t guarantees good worst case asymptotic perfmance provided the number of tasks grows as o n log n .”
• Safe Policy Improvement with Baseline Bootstrapping (2017, methodology): “Future work includes developing model-free versions of our algorithms in order to ease their use in continuous state MDP and complex real-world applications, with state representation approximation, using density networks (Veness et al., 2012; Van Den Oord et al., 2016) to compute pseudo-counts (Bel”
• Count-Based Exploration with Neural Density Models (2017, methodology): “The CTS density model (Bellemare et al., 2014) is based on the namesake algorithm, Context Tree Switching (Ve-ness et al., 2012), a Bayesian variable-order Markov model.”
• Skip Context Tree Switching (2014, methodology): “In particular, note that when K = 0 we recover the original Context Tree Switching algorithm of Veness et al. (2012).”
• Online Learning with Gated Linear Networks (2017, methodology): “The switching algorithm of Veness et al. (2012) runs in time O ( n |M| ), but was originally presented in terms of log-marginal probabilities, which requires a log-space implementation to avoid numerical difficulties.”
• Self-Correcting Models for Model-Based Reinforcement Learning (2016, unknown): “The model for each pixel was learned using Context Tree Switching (Veness et al. 2012), similar to the FAC-CTW algorithm (Veness et al.”
• Count-Based Exploration in Feature Space for Reinforcement Learning (2017, background): “Bellemare et. al. construct a Context Tree Switching (CTS) density model over the state space such that higher probability is assigned to states that are more similar to visited states [Bellemare et al. , 2016; Veness et al. , 2012].”