Little Exploration is All You Need
This work provides an incremental improvement for researchers and practitioners in reinforcement learning by enhancing exploration strategies in bandit problems.
The paper tackles the problem of exploration in multi-armed bandit algorithms by addressing the neglect of task difficulty in standard methods, introducing UCB^τ with a modified bonus term that reduces regret and risk compared to UCB and Thompson Sampling in synthetic evaluations.
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^τ$, where $τ> 1/2$, that accounts for task difficulty. Our proposed algorithm, denoted as UCB$^τ$, 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$^τ$ not only outperforms in efficacy but also exhibits lower risk across various environmental conditions and hyperparameter settings.