Online Decision-Focused Learning

Deze paper introduceert twee nieuwe online algoritmen voor decision-focused learning in dynamische omgevingen, die door middel van regularisatie en perturbatietechnieken de uitdagingen van niet-convexe en niet-differentieerbare doelfuncties overwinnen en voor het eerst wiskundige prestatiegaranties bieden.

De kern

Online Decision-Focused Learning: Een Slimme Reisgids voor Veranderende Werelden

Stel je voor dat je een reisplanner bent. Je hebt een kaart (je voorspellingsmodel) en je moet elke dag een beslissing nemen: welke route neem je om op tijd aan te komen?

In de traditionele wereld van machine learning, zou je je kaart alleen verbeteren door te kijken of je de verkeerssituaties precies voorspelt. Maar wat als je kaart perfect is, maar je toch vastzit in een file omdat je de verkeerde route koos? Of wat als de wegverhoudingen elke dag veranderen?

Deze paper introduceert een nieuwe manier van leren, genaamd Online Decision-Focused Learning. Laten we dit uitleggen met een paar simpele metaforen.

1. Het Probleem: De "Voorspel-En-Optimaliseer" Valstrik

Stel je voor dat je een chef-kok bent.

• De oude manier (Predict-then-Optimize): Je koopt eerst de beste ingrediënten in op basis van wat je denkt dat er populair is (voorspelling). Daarna probeer je een gerecht te maken. Als je ingrediënten net iets verkeerd waren, is je gerecht misschien niet lekker, zelfs als je kooktechniek perfect was. Je leert alleen uit de smaak van de ingrediënten, niet uit het eindresultaat.
• De nieuwe manier (Decision-Focused Learning): Je kijkt niet alleen naar de ingrediënten, maar je traint je smaakpapillen direct op het eindgerecht. Als het gerecht niet lekker is, pas je je inkoopstrategie direct aan, zelfs als de ingrediënten op zich "goed" leken. Je leert om de beslissing te optimaliseren, niet alleen de voorspelling.

2. De Uitdaging: Een Bewegende Doelwit

Tot nu toe werkten deze slimme systemen alleen in een statische wereld (zoals een vaste keuken met dezelfde klanten elke dag). Maar in het echte leven verandert alles:

• De klanten veranderen van smaak (de data verandert).
• De prijzen van ingrediënten schommelen (het doel verandert).
• Soms is de "beste" route vandaag morgen de slechtste.

Dit noemen ze een dynamische omgeving. Het probleem is dat de wiskunde hier heel lastig is. De "functie" die je moet optimaliseren (de kwaliteit van je beslissing) is vaak niet glad en heeft geen duidelijke helling (geen "gradient"). Het is alsof je probeert een bal te laten rollen op een oppervlak dat uit scherp afgebroken steen bestaat, in plaats van een gladde helling. Je kunt niet gewoon "de berg af lopen" zoals computers dat normaal doen.

3. De Oplossing: Twee Slimme Trucs

De auteurs van dit papier hebben twee nieuwe algoritmes bedacht om dit probleem op te lossen: DF-FTPL en DF-OGD. Ze gebruiken twee creatieve trucs:

Truc 1: De "Boter" (Regularisatie)

Omdat het oppervlak te ruw is om over te lopen, smeren ze er een laagje boter overheen (wiskundig: regularisatie).

• In plaats van te kijken naar de exacte, scherpe beslissing (bijvoorbeeld: "Ik kies alleen route A"), maken ze het een beetje vager: "Ik kies 90% route A en 10% route B".
• Dit maakt het oppervlak glad en voorspelbaar, zodat de computer de weg kan vinden. Later kunnen ze de boter weer weglaten om de scherpe beslissing te nemen.

Truc 2: De "Gokker" en de "Gids"

Omdat het oppervlak nu glad is, maar nog steeds niet perfect (het kan nog steeds holtes hebben), gebruiken ze twee strategieën:

1. DF-FTPL (De Gokker): Deze methode kijkt naar alle beslissingen die ze tot nu toe hebben gemaakt, voegt een beetje willekeur (ruis) toe, en kiest de beste route die daaruit voortkomt. Het is alsof je een gokker bent die probeert de beste strategie te vinden door veel varianten te testen. Dit werkt goed als de wereld redelijk stabiel is.
2. DF-OGD (De Gids): Deze methode is slimmer voor een chaotische wereld. Ze gebruiken een "gids" (een orakel) die een goede startpositie zoekt. Ze lopen dan een klein stapje in de richting die de gids aangeeft, maar ze kijken ook naar hoe snel de wereld verandert. Als de wereld snel verandert, passen ze hun snelheid aan. Dit zorgt ervoor dat ze altijd dicht bij de beste beslissing blijven, zelfs als de omgeving razendsnel verandert.

4. Het Resultaat: Beter Leren in de Praktijk

De auteurs hebben dit getest met een klassiek probleem: de rugzak. Stel je moet items in een rugzak doen met een gewichtslimiet. De waarde van de items verandert elke dag.

• Traditionele methoden (die alleen kijken naar voorspellingen) faalden vaak omdat ze niet zagen dat hun voorspelling, hoewel "goed", leidde tot een slechte beslissing.
• De nieuwe methoden (DF-FTPL en DF-OGD) leerden direct uit de fouten in de rugzak. Ze presteerden veel beter dan de standaardmethodes, zowel in stabiele situaties als in chaotische, veranderende situaties.

Conclusie

Kort samengevat: Deze paper leert computers niet alleen om de wereld voorspellen, maar om de wereld te begrijpen in termen van wat er gebeurt als je een beslissing neemt. Ze hebben een manier gevonden om dit te doen in een wereld die voortdurend verandert, door het wiskundige probleem even "glad" te maken en slimme strategieën te gebruiken om de beste beslissingen te vinden, zelfs als de weg er niet eenduidig uitziet.

Het is alsof je een leerling niet alleen leert de kaart lezen, maar ook hoe je het beste pad kiest als de wegen elke dag anders zijn.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Online Decision-Focused Learning", gepubliceerd als conferentiepaper bij ICLR 2026.

Probleemstelling

Traditionele machine learning-modellen worden vaak getraind om de voorspellingsnauwkeurigheid te maximaliseren (bijvoorbeeld het minimaliseren van de voorspellingsfout). In veel praktische toepassingen (zoals supply chain management, gezondheidszorg en revenue management) worden deze voorspellingen echter gebruikt als input voor een optimalisatieprobleem om beslissingen te nemen. Kleine voorspellingsfouten kunnen hierdoor leiden tot suboptimale of zelfs slechte beslissingen.

Om dit aan te pakken, is Decision-Focused Learning (DFL) ontwikkeld. Hierbij wordt het model getraind om direct de kosten van de downstream beslissing te minimaliseren, in plaats van de voorspellingsfout. Echter, bestaande DFL-methoden zijn beperkt tot batch-scenario's met stationaire data (i.i.d.).

Dit paper adresseert de uitdaging om DFL toe te passen in dynamische omgevingen waar:

1. De data-verdelingen en de doelwitfuncties in de tijd veranderen (non-stationair).
2. Het optimalisatieprobleem een bi-level structuur heeft: een buitenprobleem (het leren van de modelparameters) en een binnenprobleem (het nemen van de optimale beslissing op basis van de voorspelling).
3. De doelwitfunctie niet-differentieerbaar is (vanwege de lineaire optimalisatie in het binnenprobleem) en niet-convex. Dit maakt standaard eerste-orde optimalisatiemethoden (zoals Online Gradient Descent) onbruikbaar, omdat de gradiënten vaak nul of ongedefinieerd zijn.

Methodologie

De auteurs stellen een theoretisch kader voor online DFL en ontwikkelen twee nieuwe algoritmen om de bovengenoemde moeilijkheden (niet-differentieerbaarheid en niet-convexiteit) op te lossen.

1. Regularisatie voor differentieerbaarheid:
Om de niet-differentieerbaarheid van de beslissingsfunctie $w^*_t(\theta)$ op te lossen, wordt een regularisatieterm $R(w)$ toegevoegd aan het binnenprobleem (de lineaire optimalisatie).

• Dit maakt de oplossing $\tilde{w}_t(\theta)$ differentieerbaar.
• Voor een algemeen polytoop wordt een log-barrière gebruikt.
• Voor het simplex-geval (bijv. knapsack of portfolio selectie) wordt negatieve entropie gebruikt, wat leidt tot een softmax-mapping.
• Hierdoor wordt een surrogaatverlies $\tilde{f}_t$ gedefinieerd dat wel differentieerbaar is.

2. Benaderende Orakels voor niet-convexiteit:
Omdat het surrogaatverlies $\tilde{f}_t$ over het algemeen niet-convex is (ondanks de regularisatie), kunnen standaard convex-optimalisatie-algoritmen niet direct worden toegepast. De auteurs maken gebruik van een $\xi$-benaderend offline optimalisatie-orakel. Dit orakel kan een lokaal minimum vinden (bijvoorbeeld via Stochastic Gradient Descent) dat binnen een marge $\xi$ van het globale minimum ligt.

3. De Algoritmen:
De auteurs introduceren twee algoritmen die deze technieken combineren:

• DF-FTPL (Decision-Focused Follow-The-Perturbed-Leader):

  • Gebaseerd op het FTPL-kader.
  • Het algoritme voegt willekeurige ruis (exponentieel verdeeld) toe aan de cumulatieve verliesfunctie.
  • Het orakel minimaliseert de gestoorde cumulatieve verliesfunctie.
  • Dit levert een garantie op voor statische regret (vergelijking met de beste vaste strategie).

• DF-OGD (Decision-Focused Online Gradient Descent):

  • Gebaseerd op Online Gradient Descent, maar aangepast voor niet-convexiteit.
  • In plaats van de cumulatieve verliesfunctie te minimaliseren, minimaliseert het orakel het recente verlies.
  • De gradiënt wordt geëvalueerd op een willekeurig punt tussen de huidige parameter en het orakel-resultaat (een perturbatietechniek).
  • Dit levert een garantie op voor dynamische regret (vergelijking met een sequentie van orakels die op elk moment de beste beslissing nemen), wat essentieel is voor niet-stationaire omgevingen.

Belangrijkste Bijdragen

1. Formulering van het probleem: Het paper formaliseert online DFL als een bi-level optimalisatieprobleem in een niet-stationaire omgeving, waarbij de beslissingsmaker de kosten moet voorspellen zonder toegang te hebben tot de ware kostenfunctie tijdens het nemen van de beslissing.
2. Nieuwe Algoritmen: Introductie van DF-FTPL en DF-OGD, specifiek ontworpen om de uitdagingen van niet-differentieerbaarheid en niet-convexiteit in DFL aan te pakken.
3. Theoretische Garanties:
   • Bewijzen van sublineaire statische regret voor DF-FTPL.
   • Bewijzen van sublineaire dynamische regret voor DF-OGD.
   • Dit zijn de eerste bewezen garanties voor het online decision-focused learning-probleem. De resultaten tonen aan dat de regret afneemt met $O(T^{-1/4})$ onder bepaalde voorwaarden.
4. Omgaan met niet-convexiteit: Het paper toont aan hoe men effectief kan werken in een niet-convex kader zonder de sterke gladheidsaannames die in eerdere literatuur vaak nodig waren.

Resultaten

De auteurs evalueren hun methoden in een synthetisch experiment gebaseerd op het rugzakprobleem (knapsack problem):

• Setup: Een beslissingsnemer moet objecten selecteren op basis van voorspelde kosten. De werkelijke kosten zijn niet-stationair en niet-lineair (sinus-gedreven), wat zorgt voor een uitdagende leeromgeving.
• Benchmarks: De algoritmen worden vergeleken met:
  1. PF-OGD: Prediction-Focused Online Gradient Descent (minimaliseert voorspellingsfout, negeert beslissing).
  2. Online SPO: Smart Predict-then-Optimize (een populaire DFL-benchmark).
• Uitkomsten:
  • Zowel DF-FTPL als DF-OGD presteren significant beter in termen van totale beslissingskosten dan de benchmarks.
  • Interessant is dat de DFL-methoden een hogere voorspellingsfout (MSE) hebben dan PF-OGD, maar wel betere beslissingen nemen. Dit bevestigt de kernfilosofie van DFL: het is belangrijker om de beslissing te optimaliseren dan de voorspelling perfect te maken.
  • De methoden presteren ook beter dan Online SPO, wat aantoont dat de nieuwe perturbatie- en regularisatietechnieken effectiever zijn in deze dynamische setting.

Betekenis en Impact

Dit werk is een belangrijke stap in de evolutie van operationeel onderzoek en machine learning:

• Theoretische doorbraak: Het vult een gat in de literatuur door DFL uit te breiden van statische batch-scenario's naar dynamische online omgevingen, met strikte wiskundige garanties.
• Praktische toepasbaarheid: Veel real-world systemen (zoals dynamische prijsstelling of real-time logistiek) werken in niet-stationaire omgevingen. Deze algoritmen bieden een theoretisch onderbouwde manier om modellen te trainen die direct bijdragen aan betere beslissingen in deze context.
• Robuustheid: De resultaten tonen aan dat DFL-methoden superieur zijn wanneer de voorspellingsmodellen verkeerd gespecificeerd zijn (misspecified), wat vaak het geval is in complexe, dynamische systemen.

Kortom, het paper levert een robuust theoretisch en algoritmisch raamwerk voor het trainen van voorspellingsmodellen die direct geoptimaliseerd worden voor hun impact op beslissingen in veranderende omgevingen.