Vi anser att ett linjärt stokastiskt banditproblem där dimensionen K av den okända parametern är större än provtagningsbudgeten n. Eftersom vanliga linjära banditalgoritmer har ett beklagande av ordningen O(K ε n), är det i allmänhet omöjligt att få en sub-linjär ånger utan vidare antagande. I detta dokument utgår vi från att det är S-sparse, d.v.s. har som mest S-non-noll komponenter, och att uppsättningen av armar är enheten bollen för de två normen. Vi kombinerar idéer från Compressed Sensing och Bandit Theory för att härleda en algoritm med en ånger bunden i O (S ε n). Vi beskriver en tillämpning på problemet med att optimera en funktion som beror på många variabler men där endast ett litet antal av dem (till en början okända) är relevanta.
På samma sätt beaktade REF också de högdimensionella stokastiska linjära banditerna med gleshet, som kombinerar idéerna från komprimerad avkänning och banditteori.
Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit
{'venue': 'AISTATS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}