Thursday, Oct 4, 2:15pm, WWH-1314
SPEAKER:
Yishay Mansour, Google amd Tel Aviv University
TITLE:
Regret Minimization: Algorithms and Applications
ABSTRACT:
Consider an agent that has to select between multiple actions, where
at each time step the agent selects a distribution over actions, and
the adversary selects a vector of payoff for the actions. (The
adversary observes the agents distribution before selecting its
action.) The external regret is define as the difference between
the payoff of the best action and the agents payoff. A basic result
in regret minimization is that the agent can achieve a performance
which is near the best single action, namely, the average regret
vanishes.
In this talk we will derive regret minimization algorithms, from
basic principles. In addition we will consider the more involved
notion of internal regret, and relate it to game theoretic notations
(such as avoiding dominated actions and converging to a correlated
equilibria).
------------------------------------------------------------------------