I am studying Algorithmic Game Theory and am totally new to the topic, but wanted to clarify some items (apologies for the length beforehand). My book of reference is link.
On the topic of External Regret Minimization, in section 4.3.1, it is stated that "The Greedy Algorithm, for any sequence of losses has: $$L_{\text{Greedy}}^T\leq N\cdot L_{\min}^T+(N-1)$$ where initially: $x^1=1$, and at time $t$, $L_{\min}^{t-1}=\min_{i\in X}L_i^{t-1}$, $S^{t-1}=\{i:L_i^{t-1}=L_{\min}^{t-1}\}$, and $x^{t}=\min S^{t-1}$.
I tried to visualize this via an example, where I took:
Initial Setup:
- (N = 3) and five time steps (T = 5)
- Actions: ( X = {1, 2, 3} )
- Time steps: ( T = 5 )
- The Greedy algorithm will start by choosing action 1.
Hypothetical Loss Vectors:
- At each time step ( t ), the environment (or adversary) presents a loss vector for the actions. Let's say these are the loss vectors for each time step:
- ( t=1 ): Loss Vector = ([0, 1, 1])
- ( t=2 ): Loss Vector = ([1, 0, 1])
- ( t=3 ): Loss Vector = ([1, 1, 0])
- ( t=4 ): Loss Vector = ([0, 1, 1])
- ( t=5 ): Loss Vector = ([1, 0, 0])
Algorithm's Action and Loss:
- $t=1$, Greedy chooses $x^1 = 1$ and incurs no loss $\ell^1_1 = 0$.
- $t=2$, Greedy still chooses $x^2 = 1$ as $L^1_1 = 0$ which is the minimum loss so far, but now incurs a loss $\ell^2_1 = 1$.
- $t=3$, Greedy chooses $x^3=2$ since $L_1^2=1 $ and $L_2^2=1$ but incurs loss of $\ell^3_2 = 1$.
- $t=4$, Greedy sticks with action 2 as it has the minimum cumulative loss, but now incurs a loss $\ell^4_2 = 1$.
- $t=5$, Greedy switches to action $x^5 = 3$, as action 2 now has a higher cumulative loss. Greedy incurs no loss $\ell^5_3 = 0$.
Cumulative Loss for Greedy:
- Total loss for Greedy: $L^5_{\text{Greedy}} =3$
Best Single Action in Hindsight:
- For action 1: $L^5_1 = 0 + 1 + 1 + 0 + 1 = 3$
- For action 2: $L^5_2 = 1 + 0 + 1 + 1 + 0 = 3$
- For action 3: $L^5_3 = 1 + 1 + 0 + 1 + 0 = 3$
- Best single action loss: $L^T_{\min} = 3$ (as all actions have equal loss)
Apply Theorem 4.2:
- Theorem 4.2 states $L^T_{\text{Greedy}} \leq N \cdot L^T_{\min} + (N - 1)$.
The total loss of the Greedy algorithm over 5 time steps is indeed less than or equal to three times the best single action's loss plus two additional losses, validating Theorem 4.2 with this example.
Is this example right?