Repeated n-decision game

From Theory

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

The setting here is that the decision-maker has $n\geq 1$ fixed decision options. Each period, each decision pays off a bounded real-valued payoff, say in $[ - M, M]$ for some $M \geq 0$ . Hence the sequence of payoffs can be modeled by payoff vectors $p^1,p^2,\ldots,p^T \in [-M,M]^n$ . We allow the decision-maker to choose a probability distribution over the decisions, i.e., a member of

$\Delta_n = \{x \in \reals^n ~|~x_i \geq 0, \sum x_i = 1\}$ .

For applications in which one needs to choose a single action, this can be simulated by the randomized weighted majority, in which each period the decision maker chooses one of the decisions according to her specified distribution.

For simplicity, let us assume that the number of periods, $T$ , is known in advance (though this assumption may be removed). The decision-maker chooses $x^1,x^2,\ldots,x^T \in \Delta_n$ . The environment chooses $p^1,p^2, \ldots,p^T \in [-M,M]^n$ . The decision-maker's payoff on period $t$ is $x^t \cdot p^t = \sum_i x^t_i p^t_i$ .

Note that we make no assumption about the sequence $p^1,p^2,\ldots,p^t \in [-M,M]^n$ , other than that it is unknown but bounded. It can be arbitrary and changing. (We do not assume it is drawn independently from some distribution).

Each period, $t=1,2,\ldots,T$ :

The decision-maker (player 1) chooses $x^t \in \Delta_n$ , based on the history $p^1,p^2,\ldots,p^{t-1}$ .
The decision-maker receives payoff $x^t \cdot p^t$ , and the entire vector $p t$ is revealed to the decision maker.

Remark 1. This version is the perfect monitoring version, meaning that the decision-maker finds out the payoffs of all the decisions each period. Later we will talk about an imperfect monitoring version, in which the decision-maker finds out only the payoff of her choice that period.

Remark 2. The version is the mixed-decision version, in which the decision-maker outputs a probability distribution over decisions and achieves exactly the expected payoff.

Remark 3. Note that the in the above definition, the payoffs are not allowed to be adaptive in the sense that they cannot depend on any randomized choices that the decision-maker may make. However, in the mixed-decision version, we will consider only deterministic algorithms for making decisions. In this case, there is no need to consider adaptive payoffs.

The decision-maker's regret is defined to be:

$\mathrm{regret}=\max_{x \in \Delta_n}\frac{1}{T}\sum_{t=1}^T p^t \cdot x-\frac{1}{T}\sum_{t=1}^T p^t \cdot x^t.\,$

This is the difference between her average payoff and the average payoff achievable by the best single decision $x^* \in \Delta_n$ , where the best is chosen with the benefit of hindsight. Note that this definition does not take into account the fact that if the decision maker had chosen $x *$ each period, then the environment might have altered its choices of $p t$ . Many alternative notions of regret are natural, but the nice thing about the above definition is that, in many cases, we can bound our regret or expected regret.

The production of this material was supported in part by NSF award SES-0734780.

Retrieved from "http://wiki.cc.gatech.edu/theory/index.php/Repeated_n-decision_game"

Repeated n-decision game

From Theory

Views

Personal tools

Navigation

Search

Toolbox