Gibbs sampling with memory: Application to self-optimized routing algorithms (travail avec Pierre Coucheney).

Gibbs sampling techniques can be used to design self optimizing algorithms in a distributed system made of many agents, each of them taking actions to optimize a global cost function.
If each agent updates its action according to a Gibbs sampling law, then the whole system is known to converge to a global optimal state with probability one.
However this convergence only occurs under strigent conditions on the behavior of the system: Agent updates must happen one at a time and the valuation of the cost function must be exact.
If one of these two conditions is not satisfied (for example two agents modify their action at the same time, or the cost function valuation is noisy) then convergence may not hold or may not reach the global optimal point.
We propose a new algorithm where the previous actions of the agents are taken into account. This variant of Gibbs sampling is robust to both noisy measurements of the cost function and to any revision process (provided it has no starvation).
The dynamics induced by this algorithm is no longer Markovian. Instead, it is a stochastic approximation of the ordinary differential equation that converges to the local optimal points.
This technique is applied to self-optimizied routing optimization where its robustness is tested. Also, its speed of convergence compares well with the classical Gibbs sampling algorithm (numerically).