8.1 Regret 8.2 Basic Model 8.3 a Greedy Algorithm
Assuming that the opponent has the same stochastic strategy at each step, how should we play? Let’s formalize this: • N actions • For each step t, we choose a distribution p over the N actions • For each step, we have a loss l where l(i) ∈ [0, 1] is the loss from action i • Our loss is Ni=1 p(i)l(i) Note that we do not rely on the number of opponents or on their actions. Once we assume that the opponent is constant and does not depend on us, then the opponent’s influence is only on the cost of each action. Our goals: • Bring the loss to a minimum • Choose the best action (the opponent does not change throughout time)