Vi introducerar en studie av rättvisa i mångarmade banditproblem. Vår rättvisa definition kan tolkas som att kräva att med tanke på en pool av sökande (säg, för college antagning eller bolån), är en sämre sökande aldrig gynnad framför en bättre, trots en lärande algoritm osäkerhet över de verkliga utbetalningar. Vi bevisar resultat av två typer: För det första i det viktiga specialfallet av klassiska stokastiska banditer problem (dvs. där det inte finns några sammanhang), tillhandahåller vi en bevisligen rättvis algoritm baserad på kedjade konfidensintervall, och visar en kumulativ ånger bunden med en kubik beroende av antalet armar. Vi visar vidare att alla rättvisa algoritmer måste ha ett sådant beroende. I kombination med beklagande gränser för vanliga icke-fair algoritmer som UCB, visar detta en stark åtskillnad mellan rättvist och orättvist lärande, som sträcker sig till det allmänna kontextuella fallet. I det allmänna kontextuella fallet visar vi en snäv koppling mellan rättvisa och KWIK (Knows What It Knows) inlärningsmodell: en KWIK-algoritm för en funktionsklass kan omvandlas till en bevisligen rättvis kontextuell banditalgoritm, och omvänt kan alla rättvisa kontextuella banditalgoritmer omvandlas till en KWIK-lärande algoritm. Denna täta anslutning gör att vi kan ge en bevisligen rättvis algoritm för det linjära kontextuella bandit problemet med ett polynom beroende av dimensionen, och att visa (för en annan klass av funktioner) en värsta fall exponentiellt gap i beklagande mellan rättvisa och icke-fair lärande algoritmer.
I relaterat arbete, rättvisa begränsningar införlivas i en multi-armad bandit inställning; särskilt, armar som uppfattas ha mindre värde / ersättning bör aldrig gynnas framför bättre presterande alternativ, trots en lärande algoritm osäkerhet över de verkliga utdelningar REF.
Fairness in Learning: Classic and Contextual Bandits
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}