  In this paper, we study the strategic allocation of limited resources using a
Colonel Blotto game (CBG) under a dynamic setting and analyze the problem using
an online learning approach. In this model, one of the players is a learner who
has limited troops to allocate over a finite time horizon, and the other player
is an adversary. In each round, the learner plays a one-shot Colonel Blotto
game with the adversary and strategically determines the allocation of troops
among battlefields based on past observations. The adversary chooses its
allocation action randomly from some fixed distribution that is unknown to the
learner. The learner's objective is to minimize its regret, which is the
difference between the cumulative reward of the best mixed strategy and the
realized cumulative reward by following a learning algorithm while not
violating the budget constraint. The learning in dynamic CBG is analyzed under
the framework of combinatorial bandits and bandits with knapsacks. We first
convert the budget-constrained dynamic CBG to a path planning problem on a
directed graph. We then devise an efficient algorithm that combines a special
combinatorial bandit algorithm for path planning problem and a bandits with
knapsack algorithm to cope with the budget constraint. The theoretical analysis
shows that the learner's regret is bounded by a term sublinear in time horizon
and polynomial in other parameters. Finally, we justify our theoretical results
by carrying out simulations for various scenarios.
