**Homework number 2**

**1.
**__Symmetric game __

A symmetric
two player game has *u _{1}(*

2.
** External Regret: ** Show that a
player playing a regret minimization algorithm guarantees to himself an average
payoff of at least the minimax value minus ε
where ε>0 can be arbitrarily small (as a function of T). Namely, the
value it can guarantee in a zero-sum game against an adversary, with respect to
its utility function. [HINT: show that an action sequence has an average payoff
less than the minimax value, then
it has an external regret.]

3.
__Regret____:
__Show an example where the swap regret
is unbounded with respect to the external regret. (There is an example that
uses only *3* actions, has zero external regret and swap regret linear in *T*.)

__Clarification:__ You need to choose only a loss sequence and actions
(no adversary or algorithm). Given the loss sequence and the selected actions,
the external regret is the difference between the loss of the action sequence
and that of the loss of the best single action. The swap regret is the
difference between the loss of the action sequence and the loss of the best
function f of swapping actions.

**4.
**** Polynomial weights :** Consider the following weight update:

Show a regret
bound of *ηQ** + ln(m)/η*,
where *Q* bound the sum of square of losses of any action, i.e.,

*Q > max _{i}
∑_{t} loss^{2}(t,i)*, and

Here are the
proposed steps. Let *W ^{t}*

·
*ln**(W ^{T+1
}/W^{1}) ≥ - ηL(T,i) – ln(m)- η^{2}Q*

o
use the
inequality *ln**(1-z) ≥ -z-z ^{2}*
for z in [0,½].

·
*ln**(W ^{T+1}/W^{1})≤
-ηL_{ON}, *where

o use the inequality* ln(1+z) ≤ z*

__The
homework is due May 17__

__Hand in
your proposal for a project by May 24__