# Decision Making in Non-Stationary Environments with Policy-Augmented Search

arXiv: https://arxiv.org/abs/2401.03197 · HTML: https://mlsanity.com/paper/2401.03197/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 7 of its 27 references that are in the map.
- First posted on arXiv 6 Jan 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 7 of 7)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Non-Stationary Markov Decision Processes, a Worst-Case Approach using Model-Based Reinforcement Learning, Extended version](https://mlsanity.com/paper/1904.10090/) (2019)
- [Variational Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1905.05857/) (2019)
- [Combining Q-Learning and Search with Amortized Value Estimates](https://mlsanity.com/paper/1912.02807/) (2019)
- [Safe Reinforcement Learning with Scene Decomposition for Navigating Complex Urban Environments](https://mlsanity.com/paper/1904.11483/) (2019)
- [An Online Decision-Theoretic Pipeline for Responder Dispatch](https://mlsanity.com/paper/1902.08274/) (2019)
- [Hierarchical Planning for Dynamic Resource Allocation in Smart and Connected Communities](https://mlsanity.com/paper/2107.01292/) (2021)

## Built on by (most cited first, 4 of 4)

- [Shrinking POMCP: A Framework for Real-Time UAV Search and Rescue](https://mlsanity.com/paper/2411.12967/) (2024)
- [Challenges in Credit Assignment for Multi-Agent Reinforcement Learning in Open Agent Systems](https://mlsanity.com/paper/2510.27659/) (2025)
- [SNAPE-PM: Building and Utilizing Dynamic Partner Models for Adaptive Explanation Generation](https://mlsanity.com/paper/2505.13053/) (2025)
- [Improving Robustness of AlphaZero Algorithms to Test-Time Environment Changes](https://mlsanity.com/paper/2509.04317/) (2025)

## Abstract (arXiv)

Sequential decision-making under uncertainty is present in many important problems. Two popular approaches for tackling such problems are reinforcement learning and online search (e.g., Monte Carlo tree search). While the former learns a policy by interacting with the environment (typically done before execution), the latter uses a generative model of the environment to sample promising action trajectories at decision time. Decision-making is particularly challenging in non-stationary environments, where the environment in which an agent operates can change over time. Both approaches have shortcomings in such settings -- on the one hand, policies learned before execution become stale when the environment changes and relearning takes both time and computational effort. Online search, on the other hand, can return sub-optimal actions when there are limitations on allowed runtime. In this paper, we introduce textitPolicy-Augmented Monte Carlo tree search (PA-MCTS), which combines action-value estimates from an out-of-date policy with an online search using an up-to-date model of the environment. We prove theoretical results showing conditions under which PA-MCTS selects the one-step optimal action and also bound the error accrued while following PA-MCTS as a policy. We compare and contrast our approach with AlphaZero, another hybrid planning approach, and Deep Q Learning on several OpenAI Gym environments. Through extensive experiments, we show that under non-stationary settings with limited time constraints, PA-MCTS outperforms these baselines.