The Dependence of Effective Planning Horizon on Model Accuracy

By Nan Jiang, Alex Kulesza, Satinder Singh, Richard L. Lewis. 2015

160 citations recorded by the source corpus.

For Markov decision processes with long horizons (i.e., discount factors close to one), it is common in practice to use reduced horizons during planning to speed computation. However, perhaps surprisingly, when the model available to the agent is estimated from data, as will be the case in most real-world problems, the policy found using a shorter planning horizon can actually be better than a policy learned with the true horizon. In this paper we provide a precise explanation for this phenomenon based on principles of learning theory. We show formally that the planning horizon is a complexity control parameter for the class of policies to be learned. In particular, it has an intuitive, monotonic relationship with a simple counting measure of complexity, and that a similar relationship can be observed empirically with a more general and data-dependent Rademacher complexity measure. Each complexity measure gives rise to a bound on the planning loss predicting that a planning horizon shorter than the true horizon can reduce overfitting and improve test performance, and we confirm these predictions empirically.

Subfields: Artificial Intelligence, Reinforcement Learning

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 Reinforcement Learning

Citations in the corpus

Observe and Look Further: Achieving Consistent Performance on Atari (2018, background): “[10] Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis.”
From Importance Sampling to Doubly Robust Policy Gradient (2019, neutral): “4), and use a different discount factor γ′ (again for variance reduction (Baxter & Bartlett, 2001; Jiang et al., 2015)).”
Unifying Task Specification in Reinforcement Learning (2016, background): “The utility of learning with a smaller γ c has been previously described (Jiang et al., 2015), however, here we further advocate that enabling γ that provides subtasks is another strategy to improve learning.”
Combating the Compounding-Error Problem with a Multi-step Model (2019, methodology): “…Gal et al. , 2018], hallucinating training examples [Talvitie, 2014; Azizzadenesheli et al. , 2018; Venkatraman et al. , 2015; Oh et al. , 2015; Bengio et al. , 2015], using ensembles [Kurutach et al. , 2018; Shyam et al. , 2018], or model regularization [Jiang et al. , 2015; Asadi et al. , 2018b].”
Non-delusional Q-learning and value-iteration (2018, background): “[15] Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis.”
Beyond the One Step Greedy Approach in Reinforcement Learning (2018, methodology): “As was previously analyzed in (Petrik & Scherrer, 2009; Strehl et al., 2009; Jiang et al., 2015) and reported (François-Lavet et al., 2015), solving a MDP with a smaller discount factor is in general easier.”
Neural Architecture Search for Class-incremental Learning (2019, methodology): “Limiting the horizon acts as a complexity control method (Jiang et al. 2015) and results in only optimizing for the current distribution.”
The successor representation in human reinforcement learning (2016, background): “In the theory, the prediction timescale (known as the “planning horizon”) is controlled by the discount factor over future state occupancies in Equation 1, and need not, in general be the same as the agent’s time discount preference over delayed rewards 35 .”
Scalable methods for computing state similarity in deterministic Markov Decision Processes (2019, background): “Further, Jiang et al. (2015) demonstrate that using shorter horizons during planning can often be better than using the true horizon, especially when using a model estimated from data.”
Toybox: A Suite of Environments for Experimental Evaluation of Deep Reinforcement Learning (2019, background): “…presenting unique challenges for policy learning: • Planning Horizon Atari environments requiring temporally extended planning strategies for success, as in Frost-bite, still present challenges to deep reinforcement learning algorithms (Jiang et al., 2015; Lake et al., 2017; Farquhar et al., 2018).”
Lipschitz Continuity in Model-based Reinforcement Learning (2018, background): “One promising direction for mitigating the effects of inaccurate models is the idea of limiting the complexity of the learned models or reducing the horizon of planning (Jiang et al., 2015).”
An Introduction to Deep Reinforcement Learning (2018, unknown): “When the model available to the agent is estimated from data, the policy found using a shorter planning horizon can actually be better than a policy learned with the true horizon (Petrik and Scherrer, 2009; Jiang et al., 2015b).”
When Waiting is not an Option : Learning Options with a Deliberation Cost (2017, background): “In accordance with more general results on discounting (Petrik and Scherrer 2008; Jiang et al. 2015), τ should be aligned with the representational capacity of the system since τ → 1 involves an increasingly more difﬁcult prediction problem.”
Grounded Action Transformation for Robot Learning in Simulation (2017, methodology): “Previous work has shown that when using a model estimated from data it is better to use shorter action trajectories to avoid overﬁtting to an inaccurate model (Jiang et al. 2015).”
Value Preserving State-Action Abstractions (2020, methodology): “Recent work has continued to clarify the conditions under which state abstractions preserve value in MDPs (Jiang et al., 2015a; Abel et al., 2016), non-Markovian environments (Hutter, 2014), planning algorithms (Hostetler et al., 2014; Jiang et al., 2014; Anand et al., 2015) and lifelong RL (Abel et”
Strategic Object Oriented Reinforcement Learning (2018, methodology): “ed how planning horizon can affect planning loss (Kearns & Singh, 2002; Strehl et al., 2009). Recent study has shown that shorter planning horizons might be better when there is model inaccuracy (Jiang et al., 2015). In contrast, in this work, we studied how imperfect planning can affect explora”
Self-Tuning Deep Reinforcement Learning (2020, background): “In model-based RL, it was shown that the policy found using a smaller discount factor can actually be better than a policy learned with the true discount factor (Jiang et al., 2015).”
What can I do here? A Theory of Affordances in Reinforcement Learning (2020, background): “(Jiang et al., 2015) For any MDP M̂AFI with R̂ = R, which is an approximate model of the MDP given by the intent collection I, we have ∣∣∣∣∣∣V ∗ MI − V π∗ AFI MI ∣∣∣∣∣∣∞ ≤ 2 max π∈ΠI ||V π MI − V π M̂AFI ||∞ (17)”