A Harmonic Mean Formulation of Average Reward Reinforcement Learning in SMDPs

Technische Samenvatting: Een Harmonisch Gemiddelde Formulering van Gemiddelde Beloning Versterkend Leren in SMDP's

1. Probleemstelling

Het artikel adresseert de uitdaging van het optimaliseren van gemiddelde niet-gediskonteerde beloning in Semi-Markov Beslissingsprocessen (SMDP's) met oneindige horizonten. In tegenstelling tot standaard Markov Beslissingsprocessen (MDP's), waarbij acties een vaste tijdseenheid innemen, omvatten SMDP's acties die stochastisch zowel beloningen als variërende duur (verblijftijden) genereren. Het doel is het maximaliseren van de gemiddelde beloningsrate (beloning per tijdseenheid), in plaats van de totale opgebouwde beloning.

Bestaande modelvrije algoritmen voor deze setting, specifiek SMART en Relaxed-SMART, lijden onder kritieke beperkingen wanneer beloningen en duur niet-stationair of afhankelijk zijn:

• SMART vertrouwt op het lange-termijn steekproefgemiddelde (totale beloning gedeeld door totale tijd). Deze aanpak is breekbaar; het veronderstelt stationariteit en kan worden gedomineerd door uitschieters of falen bij het aanpassen aan regimeverschuivingen in niet-stationaire omgevingen.
• Relaxed-SMART probeert niet-stationariteit te hanteren door Exponentiële Glijdende Gemiddelden (EMA) te gebruiken voor zowel beloningen als duur, en vervolgens hun verhouding te nemen. Deze methode benadert de gemiddelde rate echter als de verhouding van rekenkundige gemiddelden. Het artikel toont aan dat deze benadering alleen wiskundig correct is als beloningen en duur onafhankelijk zijn. Wanneer ze gecorreleerd zijn (niet-lineair gerelateerd), levert de verhouding van gemiddelden een onjuiste schatting op van de ware gemiddelde rate.

2. Methodologie

De auteurs stellen een nieuwe aanpak voor gebaseerd op het Harmonisch Gemiddelde, wat de theoretisch correcte operator is voor het middelen van rates (bijvoorbeeld: snelheid = afstand/tijd).

De Beperking van het Harmonisch Gemiddelde:
Hoewel het harmonisch gemiddelde de correcte aggregatie is voor rates, is de standaarddefinitie ongeschikt voor algemeen Versterkend Leren (RL) omdat:

1. Het ongedefinieerd is voor nulwaarden (deling door nul).
2. Het de "interne" eigenschap verliest (het gemiddelde ligt tussen het minimum en maximum) wanneer waarden gemengde tekens hebben (positieve en negatieve beloningen).

De Gewijzigde Harmonisch Gemiddelde Operator ($\mathcal{H}$):
Om deze beperkingen te overwinnen, introduceren de auteurs een Gewijzigde Harmonisch Gemiddelde Operator ($\mathcal{H}$). Deze operator:

• Partitioneert de data in drie sets: positieve beloningen ($X_+$), negatieve beloningen ($X_-$) en nul-beloningen ($X_0$).
• Berekent het standaard harmonisch gemiddelde voor de positieve en negatieve subsets apart.
• Berekent een gewogen rekenkundig gemiddelde van deze resultaten, waarbij nulwaarden worden behandeld als een waarde van 0.
• Theoretische Eigenschappen: De auteurs bewijzen dat $\mathcal{H}$ een algemeen gemiddelde is (voldoet aan interniteit, idempotentie, symmetrie en monotonie) en het standaard harmonisch gemiddelde generaliseert waar laatstgenoemde gedefinieerd is. Echter, bewijzen ze dat het geen kwasi-aritmetisch gemiddelde is, wat het onderscheidt van de klasse die standaard rekenkundige, meetkundige en harmonische gemiddelden bevat.

Harmonische $R$-Learning Algoritme:
De auteurs integreren $\mathcal{H}$ in een modelvrij RL-algoritme genaamd Harmonische $R$-Learning.

• Het volgt de structurele update-regels van $R$-Learning en SMART (het updaten van $Q$-waarden gebaseerd op de marginale beloning ten opzichte van de gemiddelde rate).
• In plaats van de gemiddelde rate $\rho$ bij te werken met een eenvoudige rekenkundige EMA of een verhouding van EMA's, onderhoudt het een Exponentieel Glijdend Harmonisch Gemiddelde.
• Het algoritme houdt reciprocals van rates ($r/\tau$) bij voor positieve en negatieve beloningen apart, onderhoudt exponentiële glijdende gemiddelden van deze reciprocals en hun bijbehorende gewichten, en keert ze vervolgens om om de huidige schatting van $\rho$ te berekenen.

3. Belangrijkste Bijdragen

1. Theoretische Analyse van Bestaande Algoritmen: Het artikel toont formeel aan (via Stelling 1) dat de verhouding van rekenkundige gemiddelden (gebruikt door Relaxed-SMART) alleen gelijk is aan het harmonisch gemiddelde als de covariantie tussen beloningen en de verhouding tijd-tot-beloning nul is. In niet-stationaire of afhankelijke settings leidt dit tot onjuiste rateschattingen.
2. Nieuwe Operator: De introductie van de Gewijzigde Harmonisch Gemiddelde Operator ($\mathcal{H}$), die robuust is voor nul- en gemengde-teken beloningen terwijl het de wiskundige correctheid behoudt die vereist is voor het middelen van rates.
3. Algoritmische Generalisatie: De ontwikkeling van Harmonische $R$-Learning, een modelvrij algoritme dat bestaande $R$-Learning-varianten generaliseert naar SMDP's zonder de stationariteits- of onafhankelijkheidsaannames van SMART en Relaxed-SMART.
4. Axiomatische Bewijzen: Bewijzen die vaststellen dat $\mathcal{H}$ een algemeen gemiddelde is maar geen kwasi-aritmetisch gemiddelde, wat de wiskundige positie ervan ten opzichte van traditionele gemiddelden verduidelijkt.

4. Empirische Resultaten

De auteurs evalueerden Harmonische $R$-Learning tegen SMART en Relaxed-SMART in twee domeinen:

• Synthetische Twee-Toestand SMDP:

  • Opzet: Een doorlopende taak met twee acties. Actie A had onafhankelijke beloningen en duur. Actie B had afhankelijke, niet-stationaire beloningen en duur (met behulp van drijvende sinus/cosinus-functies met log-schaling).
  • Vinding: In settings waarbij de afhankelijkheid tussen beloning en duur de "ware" optimale actie (Actie B) moeilijk detecteerbaar maakte binnen de leertijd, faalden SMART en Relaxed-SMART (dalend naar 0% succes in moeilijkere settings). Harmonische $R$-Learning behield een hoog succespercentage over alle parametercombinaties, wat superieure robuustheid tegen niet-stationariteit en afhankelijkheid aantoont.

• Bitcoin-handel (Real-world Data):

  • Opzet: Een omgeving met hoge volatiliteit en niet-stationariteit, gebruikmakend van Bitcoin-prijzen op minuut-niveau (2012–2025). De taak omvatte kopen/verkopen met stochastische actieduur (5–45 seconden). Twee versies werden getest: één met willekeurige duur (onafhankelijk) en één waarbij de duur werd geschaald op de grootte van de beloning (afhankelijk).
  • Vinding:
    • In de onafhankelijke versie presteerden alle algoritmen vergelijkbaar, zoals verwacht door de theorie.
    • In de afhankelijke versie (waarbij de grootte van de beloning de duur beïnvloedde), presteerde Harmonische $R$-Learning significant beter dan zowel SMART als Relaxed-SMART, met een hoger winratio over 21 datasegmenten. Dit bevestigt de theoretische claim dat de benadering via verhouding-van-gemiddelden faalt wanneer beloningen en duur gekoppeld zijn.

5. Betekenis en Claims

Het artikel claimt dat Harmonische $R$-Learning een noodzakelijke correctie biedt voor RL met gemiddelde beloning in SMDP's waar de verdelingen van beloning en duur niet-stationair of afhankelijk zijn.

• Het betoogt dat eerdere methoden (SMART/Relaxed-SMART) fundamenteel gebrekkig zijn onder deze specifieke voorwaarden omdat ze vertrouwen op rekenkundige benaderingen die de koppeling tussen beloningsgrootte en tijd negeren.
• De gewijzigde harmonisch gemiddelde operator wordt gepresenteerd als het wiskundig correcte instrument voor het middelen van rates in RL, waarmee de toepasbaarheid van $R$-Learning wordt uitgebreid naar complexe, real-world scenario's zoals financiële handel waar dergelijke afhankelijkheden veelvoorkomend zijn.
• Het werk wordt gepositioneerd als een theoretische en empirische verbetering ten opzichte van de state-of-the-art voor modelvrije optimalisatie van gemiddelde beloning in semi-Markov settings, specifiek gericht op de "niet-stationaire" en "afhankelijke" gaten in de huidige literatuur.