Online Learning in Budget-Constrained Dynamic Colonel Blotto Games

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 the learner who has limited troops to allocate over a finite time horizon, and the other player is an adversary. At each stage, the learner plays a Colonel Blotto game with the adversary and strategically determines the distribution of troops among battlefields based on past observations. The adversary chooses its allocation strategy 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 payoff of the best mixed strategy and the realized payoff by following a learning algorithm while not violating the budget constraint. The learning in dynamic CBG is analyzed under the framework of combinatorial bandit and bandit 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 Edge for the path planning problem and a bandit with knapsack algorithm LagrangeBwK 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 performing simulations for various scenarios.