Regret minimization in repeated strategic interactions and in online decision problems has been extensively studied in the literatures of game theory, machine learning, and optimization. Early regret minimizing algorithms were related to the notion of fictitious play [1]}, [2]} (a.k.a. follow-the-leader), which although in its basic form does not guarantee low regret, its variant, Follow the Perturbed Leader (FTPL) [3]}, [4]}, [5]}, [6]} is known to guarantee adversarial regret of \(O(\sqrt{T})\)  in \(T\)  decisions. Another common approach for regret minimization is the multiplicative weights algorithm (see [7]} and references therein) which has been developed and rediscovered many times in many variants.
Similar ideas of regret minimization apply both in settings in which players observe full feedback on their past actions and forgone actions (the experts-advice setting) and in the multi-armed-bandit setting, where feedback is available only for the actions that were selected, and in which variants of multiplicative weights (such as EXP-3 [8]}, [9]}) have been developed.
