# Scale-free adaptive planning for deterministic dynamics & discounted rewards

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 28 references that are in the map.
- First posted on arXiv 20 Apr 2026.

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

- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014)
- [A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption](https://mlsanity.com/paper/1810.00997/) (2018)
- [Monte-Carlo Tree Search by Best Arm Identification](https://mlsanity.com/paper/1706.02986/) (2017)
- [Normalized Online Learning](https://mlsanity.com/paper/1408.2065/) (2014)
- [Blazing the trails before beating the path: Sample-efficient Monte-Carlo planning](https://mlsanity.com/paper/2604.14974/) (2026)
- [Practical Open-Loop Optimistic Planning](https://mlsanity.com/paper/1904.04700/) (2019)
- [Training Deep Networks without Learning Rates Through Coin Betting](https://mlsanity.com/paper/1705.07795/) (2017)

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

- [Planning in entropy-regularized Markov decision processes and games](https://mlsanity.com/paper/2604.19695/) (2026)

## Abstract (arXiv)

We address the problem of planning in an environment with deterministic dynamics and stochastic rewards with discounted returns. The optimal value function is not known, nor are the rewards bounded. We propose Platypoos, a simple scale-free planning algorithm that adapts to the unknown scale and smoothness of the reward function. We provide a sample complexity analysis for Platypoos that improves upon prior work and holds simultaneously over a broad range of discount factors and reward scales, without the algorithm knowing them. We also establish a matching lower bound showing our analysis is optimal up to constants.