Томпсон - образец для обучения в играх с нулевым коэффициентом

arXiv: 2610.18899v1 Аннонс Тип: перекрестное резюме: выборка Томпсона (TS) достигает логарифмического и асимптотического оптимального сожаления в классических тохастических бандитах, но его поведение при обучении с использованием нескольких агентов остается менее понятным. Мы изучаем TS в неизвестной финальной матричной игре с нулевой суммой с обратной связью Гауссианских бандитов. В рамках централизованной самопроигрышной игры TS берет одну матрицу окупаемости из заднего текста и играет баланс Nash в выбранной игре. На каждую игру с фиксированной нулевой суммой и уникальным равновесием Нэша мы показываем, что ожидаемый кумулятивный разрыв двойственности составляет $O(\sqrt T) долларов. Ставка увеличивается до $O(log T) долларов для чистого равновесия. Затем мы идентифицируем точный коэффициент $sqrt T$, который зависит только от стратегий равновесия и уровня шума. Мы также установили мини-максимум более низкую границу, соответствующую квадратной зависимости от доллара ТТ и нижней привязке к логарифмической зависимости от $T в классе игр с уникальным чистым равновесием. Эксперименты