Research map / Learning theory and algorithms / Combinatorial and search optimization
Discovering Options That Minimize Average Planning Time
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.
Proposes Average Options, an option discovery method that minimizes average shortest-path distance between all state pairs via k-medians with penalties (and a faster k-medians variant, Fast Average Options), with a worst-case (4α, 2) approximation guarantee on planning time.
Problem
Discovering temporally extended options (point options) that reduce expected value-iteration planning time averaged over all start-goal pairs in a multi-goal MDP setting.
Approach
Reduces option discovery in the multi-goal setting to the k-medians with penalties problem on an augmented graph, so that minimizing average graph distance (an upper bound on average VI iterations) yields a provable (4α, 2)-approximation; a faster k-medians variant trades the guarantee for run-time.
Key results
- Average Options achieves a worst-case (4α, 2)-approximation to the optimal option set, with α=5 for the k-MP subroutine used in experiments.
- On four discrete domains, Average Options consistently requires fewer VI iterations than Covering Options and Eigen Options; Fast Average Options tends to outperform them as environments grow larger.
- In continuous domains (Ant U-Maze, Fetch-Reach), Fast Average Options outperforms Covering Options and Eigen Options in mean planning time; Average Options gives a larger improvement but at higher computation cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Average Options instead of Covering Options or Eigen Options | Option discovery for discrete domains · 9x9 grid, Two-Rooms, Four-Rooms, Towers of Hanoi | average VI iterations to convergence | Helped |
| Use Fast Average Options instead of Covering Options or Eigen Options | Option discovery for discrete domains · Discrete domains | average VI iterations to convergence | Mixed |
| Use Fast Average Options instead of Covering Options or Eigen Options | Option discovery for continuous domains · Ant U-Maze and Fetch-Reach | average planning time | Helped |
| Replace the k-medians-with-penalties subroutine with k-medians (ablation) | Average Options · Ant U-Maze and Fetch-Reach | average planning time | Hurt |
Surprising findings
- Fast Average Options has variable performance on small discrete domains, though it generally outperforms baselines as environments grow.
Limitations
- Fast Average Options loses the worst-case approximation guarantee.
- Point options restrict initiation and termination to single states; continuous domains require ε-ball approximations.
- Theory assumes invertible-action deterministic MDPs for the main bound; stochastic extension relies on a symmetrized distance.
Experimental setup
Datasets: 9x9 grid Two-Rooms Four-Rooms Towers of Hanoi Ant U-Maze Fetch-Reach
Benchmarks: 9x9 grid Two-Rooms Four-Rooms Towers of Hanoi Ant U-Maze Fetch-Reach
Metrics: average number of value iteration steps to convergence mean planning time (random shooting actions sampled)
Baselines: Covering Options Eigen Options
Builds on: Meyerson and Tagiku (2009) k-median with penalties reduction Jinnai et al. 2019a (A-MIMO) Covering Options Eigen Options
Closest papers by meaning
- Finding Options that Minimize Planning Time (ICML 2019 · similarity 0.91)
- Efficient Planning in Large MDPs with Weak Linear Function Approximation (NeurIPS 2020 · similarity 0.86)
- Average-Reward Learning and Planning with Options (NeurIPS 2021 · similarity 0.86)
- Discovering Options for Exploration by Minimizing Cover Time (ICML 2019 · similarity 0.86)
- Planning and Learning in Average Risk-aware MDPs (NeurIPS 2025 · similarity 0.84)
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.84)
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.