Multiscale Reward Hedging from Correct Demonstrations

Technical Summary: Multiscale Reward Hedging from Correct Demonstrations

Problem Formulation
The paper addresses the problem of learning from correct demonstrations in settings where multiple actions may be optimal. Unlike standard supervised learning, the learner observes a single valid demonstration $a^*_t$ for a context $x_t$ but receives no feedback regarding whether their own prediction $\hat{a}_t$ was correct, nor do they observe the underlying reward function or the magnitude of their loss. The objective is to minimize the cumulative "hidden gap" (the difference between the reward of the optimal action and the learner's action) against an unknown reward function $r^*$.

This setting generalizes previous work on finite reward classes (Joshi et al., 2026) to continuous reward classes, a gap previously unaddressed for general continuous classes. The feedback model is distinct from online inverse optimization or standard contextual bandits because the learner never observes a reward value or a correctness bit; they only observe one valid action from an unknown set of optimal actions.

Methodology: Multiscale Reward Hedging
The core contribution is a deterministic, multiscale reward-hedging algorithm that operates without a known time horizon. The methodology relies on the following components:

1. Gap Metric and Proxies: The algorithm focuses on the optimality-gap function $g_r(x, a) = \sup_{b \in A(x)} r(x, b) - r(x, a)$. Instead of estimating the reward function directly, the learner maintains a weighted vote over a set of "tolerant binary proxies."
2. Multiscale Covering: For a sequence of accuracy scales $\epsilon_j = 2^{-j-1}$, the algorithm constructs proper $\epsilon_j$-covers ($C_j$) of the gap function class $G$. Each element $h \in C_j$ defines a proxy $q_{j,h}$ that labels an action as "good" if $h(x, a) \le \epsilon_j$.
3. Shared Vote: Rather than running separate learners for each scale (which would yield incompatible actions), the algorithm aggregates all proxies across all scales into a single weighted vote. The initial weight of a proxy at scale $j$ is proportional to $2^{-j}$.
4. Update Rule: The update is "mistake unaware." Upon observing a demonstration $a^*_t$, the algorithm updates weights based solely on the comparison between the proxy's judgment of the demonstration and the learner's prediction:
   • If the proxy calls the demonstration good but the learner's action bad, the proxy's weight doubles.
   • If the proxy calls the demonstration bad, the weight is zeroed.
   • Otherwise, the weight remains unchanged.
     This rule ensures that if the learner's action has a large gap relative to a specific scale, the weight of the proxy representing that scale increases, effectively "hedging" against that scale of error.

Key Theoretical Results

• Horizon-Free Tail Bounds: The algorithm provides a simultaneous tail bound for the number of rounds where the loss exceeds a threshold $2^{-j}$:
  $$|\{t : \ell_t > 2^{-j}\}| \le \log_2 N(G, 2^{-j-1}) + j$$
  where $N(G, \epsilon)$ is the covering number of the gap class. Integrating these tails yields a cumulative hidden gap bound independent of the time horizon $T$:
  $$\sum_{t=1}^T \ell_t \le \sum_{j \ge 1} 2^{-j} \log_2 N(G, 2^{-j-1}) + 2$$
  This sum is bounded by a metric-entropy integral, $H_{dyad}(G)$.

• Polynomial Entropy and Regret Rates:

  • For classes with polynomial covering numbers $N(G, \epsilon) \le (A/\epsilon)^d$, the total gap is bounded by $O(d \log A)$.
  • This translates to a statistical rate of $O(d/m)$ in the online-to-batch setting.
  • Linear Contextual Recommendation: For bounded linear rewards with parameter radius $B$ and menu diameter $K$, the regret is $O(d)$ for arbitrary compact menus. This is the first polynomial finite bound for arbitrary menus without structural restrictions (e.g., M-convexity), achieved via an improper predictor.
  • Low-Rank and Neural Rewards: The framework extends to low-rank bilinear rewards ($O(BKr(m+n))$) and bounded ReLU networks with explicit bounds depending on network depth and parameters.

• Computational Complexity:

  • The general algorithm is information-theoretic and may be computationally expensive due to cover enumeration.
  • However, for one-dimensional Lipschitz parameter curves (e.g., fixed-radius rank-two recommendation), the algorithm is exact and runs in polynomial time. Specifically, for fixed-radius rank-two recommendation with menu size $k$ and reward evaluation cost $C$, the time complexity is $O(kCT^2)$.

• Lower Bounds and Robustness:

  • The paper proves a matching $\Omega(d)$ lower bound for continuous classes with entropy exponent $d$, confirming the tightness of the $O(d)$ dependence.
  • A robust variant handles suboptimal demonstrations, adding only the demonstrator's cumulative suboptimality $\Delta_T$ to the regret bound.

Significance and Claims
The paper claims to resolve the open question of learning from correct demonstrations for continuous reward classes. Its primary significance lies in:

1. First Horizon-Free Guarantee for Continuous Classes: It provides the first regret bounds for continuous classes that do not depend on the time horizon $T$, relying instead on metric entropy.
2. Improper Prediction for Arbitrary Menus: It achieves $O(d)$ regret for linear contextual recommendation with arbitrary compact menus, a setting where previous proper algorithms required structural restrictions (like M-convexity) or suffered from higher dimension dependencies.
3. Efficiency in Specific Geometries: While the general vote is expensive, the paper isolates a non-trivial case (1D Lipschitz curves) where the exact algorithm is polynomial-time, bridging the gap between information-theoretic bounds and computational feasibility.
4. Empirical Validation: A reproducible stress test on MovieLens data demonstrates that the algorithm adapts to scales and improves the mean latent gap compared to both demonstrated-rating policies and proper online baselines, using only action demonstrations without observing rewards.

The author emphasizes that while the general solution is improper (the vote may not correspond to a single valid reward parameter), it successfully minimizes the target reward gap, distinguishing it from proper online inverse optimization methods that aim to estimate the reward parameter itself.