P0 [partially_resolved] Main open problem: give a minimax solution (the minimax-optimal Learner strategy and its worst-case loss) for a decision game in the bandit setting (n actions, Learner sees only the loss of the action it plays), ideally with a simple characterization like Abernethy–Warmuth–Yellin [2008b] for the hedge setting (binary losses, bound k on the loss of the best action). 'To our knowledge, no such minim | remains open: Give the exact minimax-optimal Learner strategy and worst-case loss for the n-action bandit game with binary (or [0,1]) losses under a best-action loss budget k ≥ 1 or a fixed horizon T with unconstrained losses; the only exactly solved bandit game is the noise-free game (best arm(s) suffer zero los
Q1 [open] What is a natural 'sufficient statistic' of the state of the game? In the full-information setting, the vector s recorded all relevant information, yet in the bandit setting our observations are more complex; indeed, they even depend on the previous choices we made.
Q2 [open] What is a natural 'stopping criterion' for the game? In the hedge setting we used a bound k on the loss of the best action, and it may be reasonable to keep this restriction. Yet perhaps a bound on the time of the game would give an easier analysis.
Q3 [open] In the hedge setting game, the optimal strategy can be characterized using the notion of a 'random playout', where we imagine an adversary uniformly assigning losses to the experts. Does the minimax strategy in the bandit setting admit a similar characterization?