Research map / Reinforcement learning / MDPs and planning
On Shallow Planning Under Partial Observability
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives bias-variance bounds on the planning loss as a function of the discount factor and structural MDP parameters, extends them to POMDPs, and shows with random-MDP and CartPole experiments that shorter planning horizons can help under partial observability.
Problem
Choosing the discount factor (planning horizon) in RL under partial observability: existing bounds on the planning loss are loose and ignore MDP structure, so the optimal planning horizon is poorly understood.
Approach
Introduces horizon-sensitive and empirical action variation (restricted to discordant state-action pairs) to tighten the bias bound and derive a new variance bound, yielding a planning-loss bound in terms of structural parameters; extends structural parameters to POMDPs via compressed histories and shows they are controlled by the underlying MDP's parameters.
Key results
- Mass of Blackwell discount factors decreases as observability decreases across 10^4 random MDPs (Fixed(10,3)) abstracted to 10 to 1 observations.
- Under noise sigma=0.1 on CartPole-v1, shorter discount factors can outperform gamma=0.98, with the Blackwell horizon effectively lowered.
- With sigma=1 the agent fails to learn the task regardless of discount factor.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| decrease the number of observations | random POMDPs sampled from Fixed(10,3) · Random POMDPs | Blackwell discount factor | Helped |
| decrease observability | random POMDPs sampled from Fixed(10,3) · Random POMDPs | normalized bias | Mixed |
| use shallow planning instead of long planning | PPO · Cartpole-v1, sensor noise σ=0.1 | average reward | Helped |
| increase sensor noise to σ=1 | PPO · Cartpole-v1 | learning performance | Hurt |
| use a myopic planning horizon (γ=0) | agent with a single observation · Random POMDPs, |Ω|=1 | planning horizon optimality | Helped |
Surprising findings
- Under partial observability, shallow planning (lower gamma) can outperform the long-horizon gamma=0.98 on CartPole with noisy sensors.
Limitations
- Results are limited to finite state spaces.
- Bounds are loose; the L1 distance is often 2, and the kappa reduction from partial observability may be underestimated.
- The new planning-loss bound depends on the empirical model error, which is not accessible in practice.
Experimental setup
Datasets: randomly generated MDPs Fixed(|S|,d) CartPole-v1
Benchmarks: CartPole-v1
Metrics: normalized bias Blackwell discount factor distribution normalized structural parameters average episode reward
Baselines: prior planning-loss bound with action variation Bellman-style discount bound (R_max/(1-gamma)) PPO with gamma=0.98
Builds on: Blackwell optimality action variation bound (Gheshlaghi Azar et al.) value-function variation PPO
Closest papers by meaning
- Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning (ICML 2024 · similarity 0.89)
- Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy (NeurIPS 2024 · similarity 0.88)
- Partially Observable Hierarchical Reinforcement Learning with AI Planning (Student Abstract) (AAAI 2024 · similarity 0.87)
- Provably Efficient Partially Observable Risk-sensitive Reinforcement Learning with Hindsight Observation (ICML 2024 · similarity 0.87)
- Beyond Optimism: Exploration With Partially Observable Rewards (NeurIPS 2024 · similarity 0.87)
- Provable Partially Observable Reinforcement Learning with Privileged Information (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.