# 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 Nash 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. 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?