Vi anser att online distribuerade icke-stokastiska experter problem, där det distribuerade systemet består av en koordinator nod som är ansluten till k platser, och webbplatserna är skyldiga att kommunicera med varandra via koordinatorn. Vid varje gång steg t, en av k plats noder måste välja en expert från uppsättningen {1,.., n}, och samma webbplats får information om utbetalningar av alla experter för den omgången. Målet med det distribuerade systemet är att minimera ånger vid tidshorisonten T, samtidigt hålla kommunikationen till ett minimum. De två extrema lösningarna på detta problem är: (i) Full kommunikation: Detta simulerar i huvudsak den icke-distribuerade inställningen för att få den optimala O( log(n)T ) beklagar bundna till kostnaden för T kommunikation. (ii) Ingen kommunikation: Varje webbplats kör en oberoende kopia - ångra är O( log(n)kT ) och kommunikationen är 0. Detta dokument visar svårigheten att samtidigt uppnå ånger asymptotiskt bättre än ε kT och kommunikation bättre än T. Vi ger en ny algoritm som för en glömsk motståndare uppnår en icke-trivial kompromiss: ångra O( ε k 5(1+ )/6 T ) och kommunikation O(T /k ), för något värde av 0, 1/5). Vi överväger också en variant av modellen, där koordinatorn väljer experten. I denna modell visar vi att den etiketteffektiva prognosmakaren för Cesa-Bianchi et al. (2005) ger oss redan en strategi som nästan är optimal i beklagande jämfört med kompromiss.
Därefter, Ref, studerar kommunikationen kontra ångra kompromiss i en distribuerad miljö med icke-stochastiska banditer.
Distributed Non-Stochastic Experts
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}