How to improve convergence to an equilibrium value, & damp oscillation?
I am developing a program which seeks strategies for the players A, B in any of a family of simple 2-player gambling-games. The program iterates, using a genetic algorithm to determine, from the current iteration's results, the strategies which are to play one another in the next iteration.
Below I give an overview of my algorithm. Although I've used pseudocode, I am not asking about how to code an algorithm; rather, I would like to learn what the algorithm should contain.
``` main { Strategy A[], B[]; input nIters, nStrats, maxTweak, gameRules;
A := nStrats random strategies; B := nStrats random strategies; for(t=1..nIters) { make each A play each B; for each A and each B its total score := sum of its scores in its individual games; sort the A's by total score; sort the B's by total score; v := the game's bias in favour of the best A; write v; evolveStrategies(A, nStrats, maxTweak); evolveStrategies(B, nStrats, maxTweak); } }
evolveStrategies(X, nStrats, maxTweak) { keep the best few Xs where they are; for(each of the others X[i]) { j := index of one of the best Xs; X[i] := X[j]; tweak the value of each parameter of X[i] by no more than maxTweak; } } ```
The nature of the game is that there is (with best play by A and B) a bias (positive or negative) in favour of A. Its value $V$ is what it is when A's and B's strategies are those at a <PERSON> equilibrium. Let $v$ be my program's estimate of $V$. Ideally my iterations' successive values of $v$ would converge to $V$. For some games in the relevant family, I happen to know what $V$ is; for others, I don't.
The trouble I find is that even if maxTweak is very small, the succession of $v$-values written shows oscillation with an amplitude much larger than maxTweak. Choosing a suitably large number of iterations shows that the oscillation, after an initial large rise and fall, is hardly damped if at all. 172
For example on a simple game, maxTweak=$4\times10^{-6}$ gives an initial large rise and fall, then oscillation with amplitude, peak to peak, $\approx 0.2$ and period $\approx 500000$ iterations.
One solution is to reduce maxTweak. But this entails using many more iterations, and thus more CPU time. A more radical change to my approach is needed.
Given that, a priori, the program does not know the oscillation's period or the limit value, how can my program detect the oscillation and deal with it (e.g. damp it)?
If $v$ varied as undamped simple harmonic motion, plus a constant, then $\frac{dv}{dt}$ varies as undamped simple harmonic motion about 0, so $\frac{d^3 v}{dt^3} \propto -\frac{dv}{dt}$. Since the tweaking is random, there will be small-scale oscillations due to that, as well as the larger-scale oscillation. So it seems that attempts to find higher-order derivatives of $v$ as a function of $t$ will fail.
I tried estimating the first and second derivatives $\frac{dv}{dt}$ and $\frac{d^2 v}{dt^2}$ by maintaining exponentially-weighted averages of $v$ and my estimate of $\frac{dv}{dt}$. Based on the sign of my estimate of $\frac{d^2 v}{dt^2}$ I evolved just A or B. This increased the number of iterations during $v$'s initial large rise and fall, but the following oscillation was as large and undamped as before.
One idea is to start maxTweak at a value which is not small, and adaptively reduce it. But in deciding (at each iteration) whether to reduce it or not, what should I be looking for? 172