Multi-armed bandits are sequential decision-making problems represented as a collection of probability distributions that one can sample from at every time step.

We study commitments over unreliable compound noisy channels, where parties may know the compound channel state but lack control over that state.

Take a planar graph with maximum degree d. These graphs admit a hyperfinite decompositions, where, for a sufficiently small \epsilon > 0, one removes \epsilon dn edges to get connected components of size independent of n.

In the learning literature, the performance of an online policy is commonly measured in terms of the static regret metric, which compares the cumulative loss of an online policy to that of an optimal benchmark in hindsight.