No-Regret Dynamics

Motivation. Suppose you have to choose which route to take every day driving to work. You devise a complicated strategy, but one day your neighbor and coworker, who takes the same route to work every day, says “I don’t have a strategy, I just take this one route every day.” Wouldn’t it be regretful if it turns out, in total, your route took more time than your co-worker?

def. Online Decision Making Game.

• Player has $N$ actions to choose from, $X=\{1,\dots ,N\}$
• At time $t$…
  1. Player constructs a distribution $p^t$ over the set of actions $X$
  2. Adversary chooses a loss for each action taken, $l_i\in \{0,1\}$, for every action $i\in X$ where $0$ represents no loss and $1$ represents a loss. (In our example, think of it as traffic conditions causing a delay.)
  3. Player’s distribution $p^t$ is realized into action $k^t\in X$. The player incurs a loss of $l_{k^t}^t$.
• The player’s goal is to minimize total loss, which we will define shortly.
• We play for time $t=0,\dots ,T$. Number of iterations $T$ is predetermined.

We characterize the loss if we always chose action $i$ (like how our neighbor always takes the same route) for time $t=1,\dots ,T$ as:

$$L_i^T:=\sum _{t=1}^T{l}_i^t$$

Thus we can define also:

• $L_{\text{min}}^T$ is the minimum total loss if we could only choose one action every time
• $L_{ALG}^T:={\sum }_{t=1}^T{l}_{ALG}^t$ is the total loss of player playing strategy of $ALG$, $l_{ALG}^{t=1},l_{ALG}^{t=2},\dots$.

def. External Regret. For a player playing strategy $ALG$, the regret for this strategy is:

$$R_{ALG}:=L_{ALG}^T-L_{\text{min}}^T$$

i.e. the difference between total loss of algorithm and the best total loss of one-action-every-time strategy.

Algorithms for Online Games §

alg. Greedy algorithm. This algorithm chooses the action whose one-action-fits-all-time loss is smallest

1. Initially: $x^1=1$
2. At time $t$, choose $x_i$ such that we take the minimum possible $L_i^T$. In other words:

$$x_i^t\text{ such that }={\text{argmin}}_i{L}_i^T$$

• Breaks ties determinimistically, with the action with lowest index.

Motivation. This algorithm is really bad. Instead, we can try to confuse our adversary by mixing our strategy, i.e. a randomized algorithm.

alg. Randomized Weighted Majority.

1. Initially, play $i$ with probability $p_i^1=\frac{1}{N}$ for all $i\in X$
2. At time $t$…

$$w_i^t=\{\begin{array}{ll}{w}_i^{t-1}(1-\eta )& \text{if incurred loss, i.e. }{l}_i^{t-1}=1\\ w_i^{t-1}& \text{if incurred loss, i.e. }{l}_i^{t-1}=1\end{array}$$

• where $\eta$ is the discount factor

1. Calculate this new weight for every strategy $i$, and then play $i$ with probability

$$p_i^t=\frac{w_i^t}{W^t}$$

• where $W^t:={\sum }_{i\in X}{w}_i^t$

This is a much better algorithm; in fact we can show how small its regret is.

thm. (Regret Bound of Randomized Weighted Majority) For $\eta \le \frac{1}{2}$, the loss of RWM algorithm satisfies:

$$L_{\text{RWM}}^T\le (1+\eta )L_{\text{min}}^T+\frac{\ln N}{\eta }$$

Proof. Let $F^t$ denote the fraction of weights that are discounted because they incurred a loss. We show this is equal to the expected loss at timestep $t$:

$$\begin{array}{rl}{F}^t& :=\frac{{\sum }_{i;l_i=1}{w}_i^t}{W^t}\\ & =\sum _{i;l_i=1}\frac{w_i^t}{W^t}\\ & =\sum _{i\in X}\frac{w_i^t}{W^t}{l}_i^t\\ & =\sum _{i\in X}{p}_i^t{l}_i^t\\ & =\mathbb{E}(l^t)\end{array}$$

Now, we can express $W^{t+1}$ using $F^t$ way, by splitting the summation into those that incurred a loss and those that didn’t.

$$\begin{array}{rl}{W}^{t+1}& :=\sum _{i\in X}^t{w}_i^t=\underset{(1-\eta ){\sum }_{i;l_i=1}{w}_i^t}{\underbrace{\sum _{i;l_i=1}{w}_i^t(1-\eta )}}\underset{W^t-{\sum }_{i;i{l}_i=1}}{\underbrace{\sum _{i;l_i=0}{w}_i^t}}\\ & =(1-\eta )F^t{W}^t+(W^t-F^t{W}^t)\\ & =W^t-\eta F^t{W}^t\\ & =W^t(1-\eta F^t)\end{array}$$

We can now construct the inequality:

$$\begin{array}{rlr}{\text{max}}_i{w}_i^{t+1}& \le W^{t+1}& \text{sum is greater than max}\\ (1-\eta {)}^{L_{\text{min}}^T}& \le W^{t+1}& \text{max weight is one with min loss}\\ & =W^1(1-n{F}^1)\times \cdots \times (1-n{F}^T)& W^1=N\\ & =N\prod _{t=1}^T(1-\eta F^t)& \\ L_{\text{min}}^T\ln (1-\eta )& =\ln N+\sum _{t=1}^T\ln (1-\eta F^t)& \text{Taking log on both sides}\\ & & \\ & \le \ln N+\sum _{t=1}^T\eta F^t& \forall x\in \mathbb{R},\ln (1-x)\le -x\\ & =\ln N+\eta \sum _{t=1}^T{F}^t& \\ & =\ln N+\eta L_{\text{RWM}}^T& \end{array}$$

And with some algebra and inequality: $\forall z\in \mathbb{R},-\ln (1-z)\le z+z^2$

$$L_{rwm}^T\le \frac{\ln N}{\eta }-\frac{L_{\text{min}}^T\ln (1-\eta )}{\eta }\le \frac{\ln N}{\eta }-(1+\eta )L_{\text{min}}^T$$

■