Regret

You will regret no matter what you do. The reason is that you are human.

There is this quote that I heard from the School of Life quoting another philosopher called Søren Kierkegaard:

Hang yourself or not hang ourself, you will regret both. That is the essence of human philosophy.

I am afraid of regretting to not live at my fullest potential.

In AI

The regret is the opportunity loss for one step: $\text{regret}=\text{optimal reward}-Q_t\text{I wrote this myself}$ Better notation: $l_t=\mathbb{E}[v_{\ast }-q(A_t)]$

The total regret is the total opportunity loss: $L_t=\mathbb{E}[{\sum }_{\tau =1}^t{v}_{\ast }-q(A_t)]$ where $Q_t$ is the average reward up to timestep $t$.

Game Theory

In Game Theory, the regret of not having chosen an action is the difference between the utility/reward of that action and the action we actually chose, with respect to the fixed choices of other players.

Regret is useful because it helps us understand how well an algorithm would do. With Epsilon-Greedy, we have linear regret (think about why). This is why Epsilon-Greedy is a naive algorithm, and we prefer other algorithms.

Optimistic Greedy has optimistic initialization (we initialize with the highest reward)

From CFR page: Regret is a measure of how much one regrets not having chosen an action. It is the difference between the utility/reward of that action and the action we actually chose, with respect to the fixed choices of other players.

The overall average regret of player $i$ at time $T$ is $R_i^T=\frac{1}{T}{\max }_{{\sigma }_i^{\ast }\in {\sum }_i}{\sum }_{t=1}^T(u_i({\sigma }_i^{\ast },{\sigma }_{-i}^t)-u_i({\sigma }^t))$

• where ${\sigma }_i^t$ is the strategy used by player $i$ on round $t$
• $u_i({\sigma }_i^{\ast },{\sigma }_{-i}^t)$ is utility of a strategy profile with ${\sigma }_i^{\ast }$ and ${\sigma }_{-i}^t$

Next

• I originally learned regret in the context of Reinforcement Learning and Multi-Armed Bandit, t it pops up for Regret Matching to solve Imperfect Information games