Abstract
Planning in Partially Observable Markov Decision Processes (POMDPs) typically involves a trade-off between the accuracy of closed-loop search trees and the memory efficiency of open-loop ones. We present CORAL (Counterfactual Open-loop Reasoning with Ad hoc Learning), an algorithm that bridges this gap. By treating missing observations as unobserved confounders and applying causal reasoning, CORAL enables context-aware planning within the compact structure of an open-loop tree. Experimental results on standard POMDP benchmarks demonstrate that CORAL matches the performance of state-of-the-art closed-loop planners while maintaining a significantly smaller memory footprint.
The Planning Trade-off in Uncertain Environments
Planning in uncertain environments is often modeled as a Partially Observable Markov Decision Process (POMDP). To solve these, researchers typically use Monte-Carlo Tree Search (MCTS), which generally falls into two categories:
- Closed-loop planning (e.g., POMCP): These algorithms branch on every possible observation. While accurate, the search trees become enormous, leading to the "curse of history" and massive memory consumption.
- Open-loop planning: These ignore observations during the search to keep trees small and memory-efficient. However, because they ignore the context provided by observations, they usually perform poorly, finding actions that are only "good on average" rather than tailored to the specific situation.
CORAL addresses this fundamental trade-off: achieving the high performance of closed-loop planning while retaining the memory efficiency of open-loop structures.
Methods: Causal Reasoning for Planning
CORAL treats the planning problem through the lens of Causal Multi-Armed Bandits with Unobserved Confounders (MABUC). The core insight is that even if an open-loop planner does not explicitly branch on an observation, that observation still exists as an unobserved confounder ($U$) influencing the state.
CORAL uses a two-phase online learning process to leverage this hidden information:
- Phase 1: Observational Learning. The agent uses human-provided "preferred actions" (heuristics) to learn an intent policy ($\pi_{intent}$). This policy represents what a "natural" or intuitive agent would do in a given situation.
- Phase 2: Counterfactual Learning. The agent then asks a counterfactual question: "Given that my heuristic intended to take action $a$, what would have happened if I had taken action $a'$ instead?"
By conditioning its learning on this "intent," the agent effectively uses the heuristic as a proxy for the missing observations. This allows the search to become "context-aware" without the exponential branching of traditional closed-loop trees. The algorithm employs Thompson Sampling to balance exploring new action sequences and exploiting known high-reward paths.
Key Insights and Results
The authors evaluated CORAL on four classic POMDP benchmark scenarios: Tag, RockSample [11,11] and [15,15], and PocMan.
Performance and Efficiency
- Competitive Performance: In all benchmarks, CORAL matched or nearly matched the performance of state-of-the-art closed-loop algorithms like POMCP and AR-DESPOT.
- Tree Size Reduction: CORAL achieved this performance while constructing significantly smaller search trees. While closed-loop algorithms branch exponentially with observations, CORAL's tree size grows linearly with the simulation budget.
- Superiority over Standard Open-Loop: CORAL consistently outperformed standard open-loop MCTS, even when those baselines were augmented with the same human knowledge. This confirms that the counterfactual reasoning mechanism specifically provides the performance boost.
Heuristics as Causal Proxies
The most innovative leap is using human knowledge (preferred actions) not just to prune a search tree, but as a source of causal "intent." This intent acts as a signal that captures structural properties of the environment that are otherwise hidden in open-loop setups. This allows for a "better-informed search" without the memory overhead of storing every observation-action branch.
Limitations and Future Work
CORAL's performance is dependent on the quality of the provided heuristics; while they do not need to be optimal, they must capture some underlying structure of the problem. Additionally, the algorithm requires a sufficient simulation budget (typically $n_b > 1000$) to learn a meaningful intent policy before the counterfactual phase becomes effective. Future research may explore learning the intent policy from scratch during the search and applying more complex causal models to handle intricate unobserved confounders.
Summary updated