Vi tar itu med online linjär optimering problem när åtgärder av prognosen representeras av binära vektorer. Vårt mål är att förstå omfattningen av minimax beklaga den värsta möjliga uppsättning av åtgärder. Vi studerar problemet under tre olika antaganden för återkopplingen: fullständig information, och de partiella informationsmodellerna för de så kallade "semi-bandit" och "bandit"-problemen. Vi anser att både L∞- och L2-begränsningarna för de förluster som fienden tillskriver. Vi formulerar en allmän strategi med Bregman projektioner ovanpå en potential-baserad lutning nedstigning, som generaliserar de som studeras i serien av papper György et al. Kale och al. (2010) och Audibert och Bubeck (2010). Vi tillhandahåller enkla bevis som återvinner de flesta av de tidigare resultaten. Vi föreslår nya övre gränser för semi-bandit spelet. Dessutom får vi lägre gränser för alla tre återkopplingsantaganden. Med det enda undantaget av bandit spelet, de övre och nedre gränserna är tight, upp till en konstant faktor. Slutligen besvarar vi en fråga som ställts av Koolen m.fl. (2010) genom att visa att den exponentiellt viktade genomsnittlige prognostiseraren är suboptimal mot Lě-motståndare.
Detta är den så kallade semi-bandit feedback inställning REF.
Minimax Policies for Combinatorial Prediction Games
{'venue': '24th annual conference on learning theory, 2011', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}