# Multiscale Reward Hedging from Correct Demonstrations

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 20 references that are in the map.
- First posted on arXiv 7 Aug 2026.

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

- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Contextual Inverse Optimization: Offline and Online Learning](https://mlsanity.com/paper/2106.14015/) (2021)
- [Contextual Recommendations and Low-Regret Cutting-Plane Algorithms](https://mlsanity.com/paper/2106.04819/) (2021)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets](https://mlsanity.com/paper/2602.01682/) (2026)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)
- [Learning to Answer from Correct Demonstrations](https://mlsanity.com/paper/2510.15464/) (2025)
- [Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness](https://mlsanity.com/paper/2603.20826/) (2026)
- [Tight Generalization Bounds for Noiseless Inverse Optimization](https://mlsanity.com/paper/2605.08866/) (2026)
- [Mistake-Bounded Language Generation](https://mlsanity.com/paper/2605.10809/) (2026)
- [Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models](https://mlsanity.com/paper/2602.09402/) (2026)
- [Partial Feedback Online Learning](https://mlsanity.com/paper/2601.21462/) (2026)
- [Polynomial-Time Mistake-Bounded Language Generation](https://mlsanity.com/paper/2606.16077/) (2026)
- [Online Realizable Regression and Applications for ReLU Networks](https://mlsanity.com/paper/2602.19172/) (2026)
- [Online Set Learning from Precision and Recall Feedback](https://mlsanity.com/paper/2605.09565/) (2026)

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

- [Efficient Online Inverse Optimization with O(d) Regret](https://mlsanity.com/paper/2609.13440/) (2026)
- [Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes](https://mlsanity.com/paper/2609.09809/) (2026)
- [Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights](https://mlsanity.com/paper/2609.26978/) (2026)
- [Cogentic: Multi-Agent Orchestration for Automated Proof Discovery](https://mlsanity.com/paper/2609.40324/) (2026)
- [Optimal and Efficient Online Inverse Optimization](https://mlsanity.com/paper/2610.08735/) (2026)

## Abstract (arXiv)

Learning from correct demonstrations is harder than supervised learning when many answers are correct: after predicting, the learner sees one valid answer but not whether its own answer was valid, nor any reward. Existing reward-hedging guarantees consequently assume a finite reward class. We give the first horizon-free guarantee for continuous classes. The key is to hedge in one shared vote over tolerant optimality tests at every accuracy scale. A target reward has one surviving proxy per scale, and a prediction with gap above that scale doubles the proxy. This yields the simultaneous tail bound |t:ℓt>2-j|≤ log2mathcal N(mathcal G,2-j-1)+j, where mathcal G is the class of optimality-gap functions. Integrating the tails gives cumulative hidden gap bounded by a metric-entropy integral, independently of the number of rounds. Polynomial entropy (A/ε)d gives O(dlog A) total gap and a fast O(d/m) statistical rate. For bounded linear contextual recommendation, the result is O(d) regret for arbitrary compact menus. This is the first polynomial finite bound without structural restrictions on the menus, at the price of improper prediction. Although the general vote can be expensive, it is exactly polynomial-time for one-dimensional Lipschitz parameter curves. Fixed-radius rank-two recommendation takes O(KT2) time for menus of size K. We also prove an Omega(d) lower bound, low-rank and bounded ReLU-network corollaries, and a robust theorem that adds only the demonstrator's cumulative suboptimality. A reproducible adaptive stress test illustrates the predicted scale adaptation. After factorization, an exact MovieLens audit runs in 1.7 CPU seconds across ten users and improves mean latent gap over both a demonstrated-rating policy and a proper online baseline. The learner uses only action demonstrations and never observes a reward or a loss.