SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2102.05502 · NeurIPS · 2021

On the Suboptimality of Thompson Sampling in High Dimensions

Raymond Zhang, Richard Combes

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

In this paper we consider Thompson Sampling (TS) for combinatorial semibandits. We demonstrate that, perhaps surprisingly, TS is sub-optimal for this problem in the sense that its regret scales exponentially in the ambient dimension, and its minimax regret scales almost linearly. This phenomenon occurs under a wide variety of assumptions including both non-linear and linear reward functions, with Bernoulli distributed rewards and uniform priors. We also show that including a fixed amount of forced exploration to TS does not alleviate the problem. We complement our theoretical results with numerical results and show that in practice TS indeed can perform very poorly in some high dimensional situations.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2102.05502")
get_code_for_paper("2102.05502")
have("2102.05502")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2102.05502.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2102.05502.svg)](https://syntology.ai/paper/2102.05502)

Connect an agent — have() is free.