Multiscale Reward Hedging from Correct Demonstrations

Technische Samenvatting: Multiscale Reward Hedging van Correcte Demonstraties

Probleemformulering
Het artikel behandelt het probleem van het leren van correcte demonstraties in situaties waarin meerdere acties optimaal kunnen zijn. In tegenstelling tot standaard supervised learning observeert de leerling een enkele geldige demonstratie $a^*_t$ voor een context $x_t$, maar ontvangt geen feedback over de vraag of hun eigen voorspelling $\hat{a}_t$ correct was, noch observeren zij de onderliggende beloningsfunctie of de grootte van hun verlies. Het doel is om de cumulatieve "verborgen kloof" (het verschil tussen de beloning van de optimale actie en de actie van de leerling) te minimaliseren tegenover een onbekende beloningsfunctie $r^*$.

Deze setting generaliseert eerder werk op eindige beloningsklassen (Joshi et al., 2026) naar continue beloningsklassen, een gat dat voorheen niet was geadresseerd voor algemene continue klassen. Het feedbackmodel is verschillend van online inverse optimalisatie of standaard contextuele bandits omdat de leerling nooit een beloningswaarde of een correctheidsbit observeert; zij observeren enkel één geldige actie uit een onbekende verzameling optimale acties.

Methodologie: Multiscale Reward Hedging
De kernbijdrage is een deterministisch, multiscale reward-hedging algoritme dat opereert zonder een bekende tijdshorizon. De methodologie steunt op de volgende componenten:

1. Gap Metric en Proxies: Het algoritme richt zich op de optimaliteitskloof-functie $g_r(x, a) = \sup_{b \in A(x)} r(x, b) - r(x, a)$. In plaats van de beloningsfunctie direct te schatten, onderhoudt de leerling een gewogen stemming over een verzameling "tolerante binaire proxies".
2. Multiscale Covering: Voor een reeks nauwkeurigheidsschalen $\epsilon_j = 2^{-j-1}$ construeert het algoritme passende $\epsilon_j$-covers ($C_j$) van de gap-functieklasse $G$. Elk element $h \in C_j$ definieert een proxy $q_{j,h}$ die een actie als "goed" labelt als $h(x, a) \le \epsilon_j$.
3. Gedeelde Stem (Shared Vote): In plaats van aparte leerlingen voor elke schaal te draaien (wat incompatibele acties zou opleveren), aggregeert het algoritme alle proxies over alle schalen in een enkele gewogen stemming. Het initiële gewicht van een proxy op schaal $j$ is proportioneel aan $2^{-j}$.
4. Update Regel: De update is "fout-onbewust" (mistake unaware). Bij het observeren van een demonstratie $a^*_t$ werkt het algoritme gewichten bij op basis van de vergelijking tussen het oordeel van de proxy over de demonstratie en de voorspelling van de leerling:
   • Als de proxy de demonstratie "goed" noemt maar de actie van de leerling "slecht", verdubbelt het gewicht van de proxy.
   • Als de proxy de demonstratie "slecht" noemt, wordt het gewicht op nul gezet.
   • Anders blijft het gewicht ongewijzigd.
     Dit zorgt ervoor dat als de actie van de leerling een grote kloof heeft ten opzichte van een specifieke schaal, het gewicht van de proxy die die schaal representeert toeneemt, wat effectief "hedging" toepast tegen die schaal van fouten.

Belangrijke Theoretische Resultaten

• Horizon-vrije Tail Bounds: Het algoritme biedt een simultane tail bound voor het aantal ronden waarbij het verlies de drempel $2^{-j}$ overschrijdt:
  $$|\{t : \ell_t > 2^{-j}\}| \le \log_2 N(G, 2^{-j-1}) + j$$
  waarbij $N(G, \epsilon)$ het covering number is van de gap-klasse. Integratie van deze tails levert een cumulatieve verborgen kloof-bound op die onafhankelijk is van de tijdshorizon $T$:
  $$\sum_{t=1}^T \ell_t \le \sum_{j \ge 1} 2^{-j} \log_2 N(G, 2^{-j-1}) + 2$$
  Deze som wordt begrensd door een metrische-entropie integraal, $H_{dyad}(G)$.

• Polynomiale Entropie en Regret Rates:

  • Voor klassen met polynomiale covering numbers $N(G, \epsilon) \le (A/\epsilon)^d$, is de totale kloof begrensd door $O(d \log A)$.
  • Dit vertaalt zich naar een statistische rate van $O(d/m)$ in de online-to-batch setting.
  • Lineaire Contextuele Aanbeveling: Voor begrensde lineaire beloningen met parameterstraal $B$ en menu-diameter $K$, is de regret $O(d)$ voor willekeurige compacte menu's. Dit is de eerste polynomiale eindige bound voor willekeurige menu's zonder structurele restricties (zoals M-convexiteit), bereikt via een improper voorspeller.
  • Low-Rank en Neural Rewards: Het framework breidt zich uit naar low-rank bilaterale beloningen ($O(BKr(m+n))$) en begrensde ReLU-netwerken met expliciete bounds afhankelijk van netwerkdiepte en parameters.

• Computationele Complexiteit:

  • Het algemene algoritme is informatie-theoretisch en kan computationeel duur zijn door de enumeratie van covers.
  • Echter, voor ééndimensionale Lipschitz parameter curves (bijv. fixed-radius rank-two aanbeveling), is het algoritme exact en draait het in polynomiale tijd. Specifiek voor fixed-radius rank-two aanbeveling met menu-grootte $k$ en beloningsevaluatiekosten $C$, is de tijdcomplexiteit $O(kCT^2)$.

• Lower Bounds en Robuustheid:

  • Het papier bewijst een bijbehorende $\Omega(d)$ lower bound voor continue klassen met een entropie-exponent $d$, wat de nauwkeurigheid van de $O(d)$ afhankelijkheid bevestigt.
  • Een robuuste variant handelt suboptimale demonstraties af, waarbij slechts de cumulatieve suboptimaliteit van de demonstrant $\Delta_T$ wordt toegevoegd aan de regret bound.

Betekenis en Claims
Het artikel claimt de openstaande vraag over het leren van correcte demonstraties voor continue beloningsklassen te hebben opgelost. De primaire betekenis ligt in:

1. Eerste Horizon-vrije Garantie voor Continue Klassen: Het biedt de eerste regret bounds voor continue klassen die niet afhankelijk zijn van de tijdshorizon $T$, maar vertrouwen op metrische entropie.
2. Improper Predictie voor Willekeurige Menu's: Het bereikt $O(d)$ regret voor lineaire contextuele aanbeveling met willekeurige compacte menu's, een setting waar eerdere proper algoritmen structurele restricties (zoals M-convexiteit) vereisten of leden onder hogere dimensie-afhankelijkheden.
3. Efficiëntie in Specifieke Geometrieën: Hoewel de algemene stem duur is, isoleert het papier een niet-triviaal geval (1D Lipschitz curves) waar het exacte algoritme polynomiale tijd vereist, waarmee de brug wordt geslagen tussen informatie-theoretische bounds en computationele haalbaarheid.
4. Empirische Validatie: Een reproduceerbare stress test op de MovieLens-data demonstreert dat het algoritme schalen aanpast en de gemiddelde latente kloof verbetert ten opzichte van zowel gedemonstreerde-rating policies als proper online baselines, waarbij uitsluitend actie-demonstraties worden gebruikt zonder de beloningen te observeren.

De auteur benadrukt dat hoewel de algemene oplossing improper is (de stemming komt mogelijk niet overeen met één enkele geldige beloningsparameter), het succesvol de doel-beloningskloof minimaliseert, wat het onderscheidt van proper online inverse optimalisatie methoden die proberen de beloningsparameter zelf te schatten.