# Online Learning in Budget-Constrained Dynamic Colonel Blotto Games

arXiv: https://arxiv.org/abs/2103.12833 · HTML: https://mlsanity.com/paper/2103.12833/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 46 references that are in the map.
- First posted on arXiv 23 Mar 2021.

## Builds on (most cited first, 11 of 11)

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [From Duels to Battefields: Computing Equilibria of Blotto and Other Games](https://mlsanity.com/paper/1603.00119/) (2016)
- [Defense Against Advanced Persistent Threats in Dynamic Cloud Storage: A Colonel Blotto Game Approach](https://mlsanity.com/paper/1801.06270/) (2018)
- [Faster and Simpler Algorithm for Optimal Strategies of Blotto Game](https://mlsanity.com/paper/1612.04029/) (2016)
- [Generalized Colonel Blotto Game](https://mlsanity.com/paper/1710.01381/) (2017)
- [Combinatorial Bandits for Sequential Learning in Colonel Blotto Games](https://mlsanity.com/paper/1909.04912/) (2019)

## Built on by (most cited first, 1 of 1)

- [HGFormer: A Hierarchical Graph Transformer Framework for Two-Stage Colonel Blotto Games via Reinforcement Learning](https://mlsanity.com/paper/2506.08580/) (2025)

## Abstract (arXiv)

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.