Rationality from Irrationality Addendum 2: Adversary Robust Learning

One potentially unsatisfying aspect of the convergence result given in part 4 is that being based on the regret matching strategy, it is not robust against adversarial play. But recall from part 3 that if agents play according to the Blackwell strategy, their strategy will be in the limit a best response (in the sense of correlated equilibrium) to the other player’s limiting strategy, regardless of what an adversarial opponent tries to do (although admittedly, the adversarial opponent may still be able to steer the game towards the worst correlated equilibrium for the agent).

An idea we will pursue here is the following: what if an agent attempts to play the Blackwell strategy, but must estimate the regrets used to construct the the Blackwell strategy. There is good reason to hope that this strategy is viable. To see this, recall that in the proof of the Blackwell theorem, we ended up with the estimate

$\frac1{t+1} \sum_{\tau \leq t+1}\lambda_t \cdot (v(s_\tau) - F(D_\tau)) \leq \frac1{t+1} \sum_{\tau \leq t} \lambda_\tau \cdot(v(s_\tau) - v(q_\tau))$

since by construction, $s_\tau \sim q_\tau$ , we have that this forms a martingale difference sequence, and since finiteness of the game bounds this martingale difference sequence, we in fact used the Azuma-Hoeffding inequality to show that it goes to 0. When we have to estimate regrets, $q_\tau$ is not known exactly and must be estimated by $\tilde q_\tau$ . If we write $q_\tau = \tilde q_\tau + \varepsilon_t$ and plug into the above, we now need to show that

$\frac1{t+1} \sum_{\tau \leq t+1}\lambda_t \cdot (v(s_\tau) - F(D_\tau)) \leq \frac1{t+1} \sum_{\tau \leq t} \left(\lambda_\tau \cdot(v(s_\tau) - v(\tilde q_\tau)) + \varepsilon_\tau\right)$

Again, the first term in the sum goes to zero by Azuma-Hoeffding, so we only need the estimation error part to also go to 0. But notice that we do not require a very fast rate of convergence at all. In particular, $\varepsilon_t = o(1)$ clearly suffices, so any strongly consistent estimator of $q_\tau$ will do, no matter how slow the rate. Unfortunately, this idea comes with its own technical difficulties. Recall from theorem A that the Blackwell strategy took the form of solving for the an eigenvector corresponding to the first eigenvalue of the stochastic transition matrix:

$M(j,k) = \begin{cases}\frac1\mu R_t^i(j,k),\quad & j\neq k\\ 1 - \frac1\mu \sum_{k' \neq j} R_t^i(j,k'),\quad & j = k\end{cases}$

If the regrets converge to 0, $M(j,k)$ converges towards the identity matrix. At first glance, this leads to a problem because the first eigenvector mapping is discontinuous and undefined (since there are multiple eigenvectors) at the identity. This in turn raises the concern that small errors in estimating regrets will lead to large errors in estimating the Blackwell strategy. It turns out, however, that even though the Blackwell strategy mapping is discontinuous in regrets, the inner product $R^i_t \cdot \omega_{t+1}(q(R^i_t),s^{-i})$ can still be controlled. More specifically, let $\hat R_t^i(j,k) = R_t^i(j,k) + \varepsilon(j,k)$ for all pairs of strategies $j,k$ . Let $q_t$ solve the recurrence $q_t(j) = \frac{\sum_{k\neq j} q_t(k) \hat R_t^i(k,j)}{\sum_{k\neq j} \hat R_t^i(j,k)}$ as in part 3 (except with estimated regrets $\hat R_t$ instead of actual regrets). As before, we have

$R^i_t\cdot \omega_{t+1}(q_t, s^{-i}) = \sum_j \alpha(j) u^i(j,s^{-i}), \quad \alpha(j) = \sum_{k\neq j} q_t(k) R_t^i(k,j) - q_t(j) \sum_{k\neq j} R_t^i(j,k)$

Recall that when we choose an exact Blackwell strategy, $\alpha(j) = 0$ for all $j$ . For small errors in estimating regret, we can make the following computation for $\alpha(j)$ :

$\alpha(j) = \sum q_t(k)R_t^i(k,j) - q_t(j)\sum R_t^i(j,k)$

$= \sum q_t(k)[R_t^i(k,j) + \varepsilon(k,j)] - q_t(j) \sum[R_t^i(j,k) + \varepsilon(j,k)]$

$+ \sum q_t(k) \varepsilon(k,j) - q_t(j) \sum \varepsilon(k,j)$

The terms in the middle line vanish by how we chose $q_t$ while the terms in the last line are bounded by a constant $C$ times $||\varepsilon||$ where $||\cdot||$ is the max norm (this constant can be chosen to be independent of whatever we want because the game is finite). We can now plug these estimates back into the proof of Blackwell’s theorem to obtain:

Lemma 1: Let $\hat R_t(j,k) \overset{a.s.} \to R_t(j,k)$ . Then the Blackwell strategy with regrets $\hat R_t$ instead of $R_t$ converges to a correlated best response regardless of what the opponent plays.

Proof: Let $\varepsilon(j,k) = R_t(j,k) - \hat R_t(j,k)$ . From the proof of the Blackwell theorem, we just need to show that the sum

$\frac1{t+1} \sum_{\tau \leq t+1} \lambda_t \cdot (v(s_\tau) - F(D_\tau))$

goes to 0 for large $t$ . Since our strategy at time $t$ is assumed to be the Blackwell strategy corresponding to $\hat R_t(j,k)$ , and in light of the estimates above, we have that this is bounded by

$\frac1{t+1}\sum_{\tau \leq t}\left[\lambda_\tau\cdot(v(s_\tau)-v(q_\tau)) + O(||\varepsilon||)\right]$

But since by assumption $||\varepsilon|| = o_{a.s.}(1)$ , we have

$\frac1{t+1}\sum_{\tau \leq t}\left[\lambda_\tau\cdot(v(s_\tau)-v(q_\tau)) + o_{a.s.}(1)\right]$

Then finishing as in the proof of the Blackwell theorem, we get our desired result.

We have essentially shown that an estimated Blackwell algorithm converges in the presence of an “oracle” that gives us asymptotically correct information about what the regret is. In practice, we will actually have to construct the oracle $\hat R_t$ from data. In particular, we will consider strategies similar to in part 4: with probability $1 - \delta_t$ , play the estimated Blackwell strategy (exploitation), and with probability $\delta_t$ , play according to the uniform distribution (exploration). To close, we will need to bound the possible error in the exploration periods. This is relatively straightforward. By the strong law of large numbers for dependent processes, we need that it suffices to set the exploration parameter $\frac1{\delta_t} = o\left(t\right)$ . But in order to get convergence to a correlated best response, it is clearly necessary and sufficient that we also have $\delta_t \to 0$ . Fortunately, a wide variety of exploration strategies satisfy both of these. For example, letting $\delta_t \sim t^{-\gamma}$ where $0 < \gamma < 1$ will work. Summarizing,

Theorem 2: Let $\delta_t \in (0,1)$ be such that $\delta_t \to 0$ as $t \to \infty$ , but $t\delta_t \to \infty$ as $t\to\infty$ . For individual $i$ , construct estimated regrets as in part 4, and let $\hat R_t(j,k)$ be the estimated regrets obtained from the IPW estimator for regret discussed in part 4. Consider the following strategy: with probability $\delta_t$ , play any action with uniform probability. Otherwise, play according to any Blackwell strategy corresponding to $\hat R_t(j,k)$ . Then regardless of what the opponents play, $i$ ‘s empirical distribution of play will converge almost surely to a correlated best response to the empirical distribution of the opponent’s play.

While Hart and Mas-Colell preferred strategies that were maximally simple, in this post, I considered the extent to which it is possible to trade off some of this simplicity for more robustness. I find that indeed, it is possible, even when players do not know the structure of the game a priori.

For me, the results presented here are relevant along two dimensions. First, implementing a Blackwell algorithm numerically is not terribly sophisticated. In particular, since it can be described as the stationary distribution of some stochastic matrix, this vector can be computed to arbitrary precision with some basic linear algebra. It is therefore not implausible that an evolutionary or competitive process will be able to select a learner that is marginally more complex, but substantially more adversarially robust. Second, making the above algorithms practical may be a useful direction for thinking about how to run and analyze experiments in adversarial settings, which may be a useful model of how learning ought to occur in modern firms. Some interesting directions for further inquiry in the future include:

Can the rates of convergence be estimated? Are there regularizations we can make and corresponding strategies that do not converge arbitrarily slowly?
The setting considered here was maximally “reduced form” in that our agents know literally nothing about the game. How can we construct agents who are able to make use of whatever prior knowledge they might have to speed up convergence?
In our current setting, the same game is played ad infinitum, but rounds do not directly affect each other across time (except insofar as previous rounds shape strategy adopted in subsequent rounds). Do learning results like this hold in more dynamic game settings?

Edit: To help visualize the results here better, I have written a script that implements the estimated Blackwell algorithm described above for an arbitrary game that the user specifies. The code can be found here. Give it a try! Specify a game and try to minimize the average utility of the opponent.

Rationality from Irrationality Addendum 2: Adversary Robust Learning

Published by statsmodel

Leave a comment Cancel reply

Share this:

Related

Published by statsmodel

Leave a comment Cancel reply