Little Exploration is All You Need
Henry H. H. Chen Jiaming Lu
The prevailing principle of "Optimism in the Face of Uncertainty" advocates
for the incorporation of an exploration bonus, generally assumed to be
proportional to the inverse square root of the visit count ($1/\sqrt{n}$),
where $n$ is the number of visits to a particular state-action pair. This
approach, however, exclusively focuses on "uncertainty," neglecting the
inherent "difficulty" of different options. To address this gap, we introduce a
novel modification of standard UCB algorithm in the multi-armed bandit problem,
proposing an adjusted bonus term of $1/n^\tau$, where $\tau > 1/2$, that
accounts for task difficulty. Our proposed algorithm, denoted as UCB$^\tau$, is
substantiated through comprehensive regret and risk analyses, confirming its
theoretical robustness. Comparative evaluations with standard UCB and Thompson
Sampling algorithms on synthetic datasets demonstrate that UCB$^\tau$ not only
outperforms in efficacy but also exhibits lower risk across various
environmental conditions and hyperparameter settings.