  The Colonel Blotto game is a renowned resource allocation problem with a
long-standing literature in game theory (almost 100 years). However, its scope
of application is still restricted by the lack of studies on the
incomplete-information situations where a learning model is needed. In this
work, we propose and study a regret-minimization model where a learner
repeatedly plays the Colonel Blotto game against several adversaries. At each
stage, the learner distributes her budget of resources on a fixed number of
battlefields to maximize the aggregate value of battlefields she wins; each
battlefield being won if there is no adversary that has higher allocation. We
focus on the bandit feedback setting. We first show that it can be modeled as a
path planning problem. It is then possible to use the classical COMBAND
algorithm to guarantee a sub-linear regret in terms of time horizon, but this
entails two fundamental challenges: (i) the computation is inefficient due to
the huge size of the action set, and (ii) the standard exploration distribution
leads to a loose guarantee in practice. To address the first, we construct a
modified algorithm that can be efficiently implemented by applying a dynamic
programming technique called weight pushing; for the second, we propose methods
optimizing the exploration distribution to improve the regret bound. Finally,
we implement our proposed algorithm and perform numerical experiments that show
the regret improvement in practice.
