I am reading this book. In chapter 7, section 7.5 page 240 (in the pdf), the authors defined (definition 7.5.1) the regret as being the difference between the average per-period reward the agent received up until time $t$ and the average per-period reward the agent would have received up until time $t$ had he played pure strategy $s$ instead, i.e., $\mathrm{Regret}=\alpha^t-\alpha^t(s)$.

I do not get this definition of regret. For me it looks the other way around, i.e., $\mathrm{Regret}=\alpha^t(s)-\alpha^t$. I also looked for definitions in the internet and I am really lost now.

Can you please explain to me what I am missing here? Could the authors be wrong in the definition (since it is uncorrected manuscript)?


It does appear to be a mistake in this pdf version of the book, where the authors are dealing with rewards: The regret should be the reward that would have been gained for playing s minus the actual gain.

Note that often this is set up with losses (rather than rewards) so that the regret would be the incurred loss minus the loss that would have been incurred under some pure strategy.

For a given pure strategy s, the regret for not having played s should be 0 if one's choice gave the same payoff as s, positive if it was worse (i.e., lower in a rewards setting, higher in a losses setting) than s, and negative if it was better than s.

Commonly one defines the regret as the regret for not having played the best pure strategy (given the choices of others). This will be non-negative, and 0 if and only if the current choice is optimal.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.