Multiscale Reward Hedging from Correct Demonstrations

• URL: http://arxiv.org/abs/2608.06825v1
• Date: Fri, 07 Aug 2026 05:36:22 GMT
• Title: Multiscale Reward Hedging from Correct Demonstrations
• Abstract summary: Existing reward-hedging guarantees assume a finite reward class.<n>Key is to hedge in one shared vote over tolerant optimality tests at every accuracy scale.
• Score: 1.14219428942199
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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:\ell_t>2^{-j}\}|\leq \log_2\mathcal 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(d\log 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(KT^2)$ time for menus of size $K$. We also prove an $Ω(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.

Related papers

• Optimal Rates for Learning with Monotone Adversaries [7.053805156684374]
  A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice.<n>Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable.<n>Larsen, Pabbaraju, and Shetty, who introduced this model, show that empirical risk minimization attains expected error $O((d/n)log(n/d))$ for classes of VC dimension $d$.
  arXiv  Detail & Related papers  (2026-08-06T17:45:32Z)
• An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
  We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere.<n>Our guiding principle is that its maximizers are rounding candidates.
  arXiv  Detail & Related papers  (2026-08-03T17:58:00Z)
• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
  We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability.<n>Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning.<n>We also highlight several open questions on quantitative sample complexity and evaluability.
  arXiv  Detail & Related papers  (2026-05-13T15:41:30Z)
• Post-Training with Policy Gradients: Optimality and the Base Model Barrier [27.674563695368665]
  We study post-training linear autoregressive models with outcome and process rewards.<n>We prove that variants of policy gradient (PG) can achieve likelihood $1 - varepsilon$ with an essentially minimax optimal number of reward queries.
  arXiv  Detail & Related papers  (2026-03-07T00:25:53Z)
• Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games [60.871651115241406]
  A considerable chasm has been looming for decades between theory and practice in zero-sum game solving through first-order methods.<n>We propose a new scale-invariance and parameter-free variant of PRM$+$, which we call IREG-PRM$+$.<n>We show that it achieves $T-1/2$ best-iterate and $T-1$ optimal convergence guarantees, while also being on par with PRM$+$ on benchmark games.
  arXiv  Detail & Related papers  (2025-10-06T00:33:20Z)
• Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss [33.18537822803389]
  We show that whenever the topologies of $L2$ and $Psi_p$ are comparable on our hypothesis class $mathscrF$, $mathscrF$ is a weakly sub-Gaussian class.<n>Our result holds whether the problem is realizable or not and we refer to this as a emphnear mixing-free rate, since direct dependence on mixing is relegated to an additive higher order term.
  arXiv  Detail & Related papers  (2024-02-08T18:57:42Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  We show that our algorithm achieves an $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ are the cardinalities of the state and action spaces
  arXiv  Detail & Related papers  (2023-05-15T05:37:32Z)
• Variance-aware robust reinforcement learning with linear function approximation with heavy-tailed rewards [6.932056534450556]
  We present two algorithms, AdaOFUL and VARA, for online sequential decision-making in the presence of heavy-tailed rewards. AdaOFUL achieves a state-of-the-art regret bound of $widetildemathcalObig. VarA achieves a tighter variance-aware regret bound of $widetildemathcalO(dsqrtHmathcalG*K)$.
  arXiv  Detail & Related papers  (2023-03-09T22:16:28Z)
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation [92.99933928528797]
  We study the model-based reward-free reinforcement learning with linear function approximation for episodic Markov decision processes (MDPs) In the planning phase, the agent is given a specific reward function and uses samples collected from the exploration phase to learn a good policy. We show that to obtain an $epsilon$-optimal policy for arbitrary reward function, UCRL-RFE needs to sample at most $tilde O(H4d(H + d)epsilon-2)$ episodes.
  arXiv  Detail & Related papers  (2021-10-12T23:03:58Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.