Lipschitz multi-armed bandit (MAB) problem generaliserar den klassiska multi-armad bandit problem genom att anta att en ges sida information som består av en priori övre gränser på skillnaden i förväntad vinst mellan vissa par av strategier. Klassiska resultat av Lai-Robbins [28] och Auer et al. [3] innebär en logaritmisk ånger bundet för Lipschitz MAB-problemet på ändliga metriska utrymmen. Nya resultat på kontinuumarmed bandit problem och deras generaliseringar innebär lägre gränser för ε t, eller starkare, för många oändliga metriska utrymmen såsom enhetsintervall. Är denna dikotomi universell? Vi bevisar att svaret är ja: för varje metriska utrymme, är den optimala ångern av en Lipschitz MAB algoritm antingen avgränsas ovan av någon f  på (log t), eller avgränsas nedan av någon g  på o ( ε t). Kanske förvånande, denna dikotomi sammanfaller inte med skillnaden mellan finita och oändliga metriska utrymmen; istället beror det på om slutförandet av den metriska rymden är kompakt och räknabar. Våra bevis kopplar ihop övre och nedre gräns tekniker i online-inlärning med klassiska topologiska föreställningar såsom perfekta uppsättningar och Cantor-Bendixson teorem. Vi anser också fullfeedback (även känd som bestexpert) version av Lipschitz MAB problem, kallas Lipschitz experter problem, och visar att detta problem uppvisar en liknande dikotomi. Vi fortsätter att ge nästan matchande övre och nedre gränser på ånger i Lipschitz experter problem på oräkneliga metriska utrymmen. Dessa gränser är av formen till (t γ ), där exponenten γ  och [ 1 2, 1] beror på det metriska utrymmet. För att karakterisera detta beroende introducerar vi ett nytt dimensionalitetsbegrepp som är anpassat till expertproblemet. Slutligen visar vi att både Lipschitz banditer och Lipschitz experter problem blir helt intractable (i den meningen att ingen algoritm har ångra o(t)) om och endast om slutförandet av det metriska utrymmet är non-compact.
Den lägre gränsen i REF innebär inte heller en lägre gräns för vårt problem med en specifik vinst.
Sharp dichotomies for regret minimization in metric spaces
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}