  We consider a dynamic Colonel Blotto game (CBG) in which one of the players
is the learner and has limited troops (budget) to allocate over a finite time
horizon. At each stage, the learner strategically determines the budget and its
distribution to allocate among the battlefields based on past observations. The
other player is the adversary, who chooses its budget allocation strategies
randomly from some fixed but unknown distribution. The learner's objective is
to minimize the regret, which is defined as the difference between the optimal
payoff in terms of the best dynamic policy and the realized payoff by following
a learning algorithm. The dynamic CBG is analyzed under the framework of
combinatorial bandit and bandit with knapsacks. We first convert the dynamic
CBG with the budget constraint to a path planning problem on a graph. We then
devise an efficient dynamic policy for the learner that uses a combinatorial
bandit algorithm Edge on the path planning graph as a subroutine for another
algorithm LagrangeBwK. A high-probability regret bound is derived, and it is
shown that under the proposed policy, the learner's regret in the
budget-constrained dynamic CBG matches (up to a logarithmic factor) that of the
repeated CBG without budget constraints.
