Learning Multi-Timescale Abstractions for Hierarchical Combinatorial Planning

The combination of exponentially large action spaces, stochastic dynamics, and long-horizon decision-making under limited resources makes Sequential Stochastic Combinatorial Optimization (SSCO) particularly challenging for reinforcement learning. Hierarchical Reinforcement Learning (HRL) offers a natural decomposition, but it places the high-level policy in a Semi-Markov Decision Process (SMDP) where actions have variable durations, making it difficult to learn a world model that is suitable for planning. We introduce a model-based hierarchical framework for sequential stochastic combinatorial decision-making that directly addresses this issue. Our method combines a latent-space tree-search planner with an SMDP-aware world model for variable-duration decisions. A multi-timescale objective structures the latent dynamics so that transition magnitudes reflect the effective temporal scales of abstract actions, enabling efficient lookahead under adaptive temporal abstraction. We further learn a subgoal-conditioned budget policy jointly with the world model to support context-aware resource allocation. Across challenging SSCO benchmarks, our method outperforms strong baselines.

Many real-world planning problems require making a series of decisions under uncertainty while using limited resources. For example, an agent may need to decide not only what goal to pursue next, but also how much effort or budget to spend on it. This is difficult because some goals take only a few steps to complete, while others may require many steps, and poor early choices can affect the rest of the plan. We propose a learning-based planning method that handles these variable-length decisions explicitly. Instead of planning over every small action, the method learns higher-level subgoals and searches over them. It also learns how much budget to allocate to each chosen subgoal. A key part of the method is a learned internal model in which short and long subgoals are represented differently, so the planner can reason about their expected temporal scale without manually specifying how long each one should take. This makes it possible to plan more efficiently in large, uncertain decision problems with limited resources. The approach helps bridge detailed low-level action choices and longer-term strategic planning.