# Regularized Fictitious Play

https://colab.research.google.com/drive/1NN9TjZvTbljT_aYk8h0UWt0Rlok17Cq0#scrollTo=CImYKBzH6U4F

* Polyak averaging avec nn pour baselines
* écrire les équations avec la KL pour la 1ere forme de moyennage
* regarder comment remplacer la 2eme forme de moyennage
* fictitious play mirror descent + follow the (regularized) leader (et regarder applications)
* regarder toujours sur le matrix game avec représentation linéaire
* (regarder des généralisations)
* poker (nfsp) -> openspiel
* mettre Julien Perolat dans la boucle
* discuter avec Sarah Perrin FP meanfield
* Breaking the Curse of Many Agents: Provable Mean Embedding Q-Iteration for Mean-Field Reinforcement Learning

$$
\max p^T R q \\
\max <p, Rq> + \lambda KL(p, p_{t-1}) \\
$$

### https://arxiv.org/pdf/2002.08456.pdf

FoReL :
$$ \pi_t = argmax_p <v,p> - \; \phi(p) $$
Le papier généralise un résultat de (Mertikopoulos et al. 2018) pour les jeux *monotones* séquentiels à information imparfaite, en montrant que FoReL pour une reward qui ne dépend pas de la politique donne une politique *poincaré-récurrente* et donc ne converge pas : la politique obtenue retourne toujours aux alentours du point de départ.

Modification suggérée (reward policy-dependant) :
$$ R^i(a) = r^i(a^i) - \eta \log \frac{\pi^i(a^i)}{\mu^i(a^i)} + \eta \log \frac{\pi^{-i}(a^{-i})}{\mu^{-i}(a^{-i})} $$
Pour $\mu$ quelconque de support complet.

Dans ce cas, par des arguments de Lyapunov, il est démontré que FoReL converge exponentiellement vite si la régularisation est l'entropie.
Mais pas vers l'équilibre de Nash du jeu original !

Pour résoudre le problème, la procédure est de construire une séquence de $\pi_t$ optimisées en choisissant $\mu_t = \pi_{t-1}$.

Alors $\pi_t$ converge vers l'équilibre de Nash du jeu original quand $t\to +\infty$

* Mertikopoulos, P., Papadimitriou, C., and Piliouras, G. Cy-cles in adversarial regularized learning. InACM-SIAMSymposium on Discrete Algorithms (SODA), 2018.

==

Matthieu Geist
4:16 PM
https://arxiv.org/abs/1910.09322
Matthieu Geist
4:34 PM
Multiplicative weights update inzero-sum games: https://dl.acm.org/doi/abs/10.1145/3219166.3219235

http://people.csail.mit.edu/costis/6853fa2011/lec5.pdf
Adaptive game playing using multi-plicative weights

#regarder le papier munchausen (matthieu)

est-ce que la kl entre réseaux successifs est équivalente au moyennage entre res. demander à julien ce qu'il a voulu dire

- polyak averaging des poids du réseau.

===
FP synchrone et asynchrone :
https://epub.wu.ac.at/5588/1/2007_JET.pdf

jsp :
http://cs.brown.edu/people/amy/papers/icml.pdf

fp vs counterfactual regret min :
https://arxiv.org/pdf/2001.11165.pdf

same, de lazaric :
http://researchers.lille.inria.fr/~lazaric/Webpage/MVA-RL_Course17_files/regret_games.pdf

variante de fictitious play "hanent consistent":
https://ambujtewari.github.io/research/li18sampled.pdf

cours sur cfr :
http://modelai.gettysburg.edu/2013/cfr/cfr.pdf

----

Différents algos de fictitious play :
* synchrone / asynchrone
* argmax / softmax / moyennage
* weighted exponentiel / vanilla
* counterfactual regret (retrancher la valeur du coup joué, ajouter à la somme, passer dans un relu, sampler)

Différentes implems :
* self-play pur (pour jeux antisymétriques)
* sampler les actions et observer à chaque fois effectivement la colonne jouée par l'adversaire.
* VS Observer Rpi_adv
* Moyenner les policies ou calculer la distrib empirique.

Variantes KL :
- ajouter une entropie
- mettre un lambda devant la KL (une fois le pb d'opt résolu, c'est équivalent à diviser les rewards par lambdas)
- / faire varier ce lambda

Variantes moyennage global :
- $\frac{1}{t} x + (1-\frac{1}{t}) old$
- $\alpha x + (1-\alpha) old$

Le tout appris par une policy.
Mais deux possibilités :
- apprendre $f_{\theta}(s,a)$ ou apprendre $f_{\theta}(s)$

Différentes métriques :
* exploitabilité
* convergence vers solution du pb d'optimisation pour l'étape intérieure à une itération de FP
* convergence de la moyenne vers la solution
* dynamique de la politique moyenne (graphique $\pi[1] = f(\pi[0])$)

Nouvelle idée :
$\pi(z,.)$ entrainé en self-play avec $obs = R \cdot \pi(z,\cdot)$.

fictitious play avec reconnaissance de motifs !!
https://www.irit.fr/EUMAS2013/Papers/eumas2013_submission_17.pdf

xfp/fsp http://proceedings.mlr.press/v37/heinrich15.pdf

deux algorithmes sont présentés : xfp et fsp. Les deux permettent d'apprendre une behavorial policy au lieu de convertir le jeu en forme normale.
interestingly, pour fsp ils samplent selon notre équation de la moyenne.
aussi, la formule qu'ils utilisent pour convertir behavorial<=>forme normale n'est pas reprise dans nfsp il me semble (à part par l'anticipatory dynamics).

nfsp https://arxiv.org/abs/1603.01121
revient à jouer parfois des trajectoires avec la politique moyenne,
et parfois avec la politique epsilon-greedy(Q) (best reponse).
(en self-play).
Ca veut dire que Q est calculée en gros sur la moyenne (pour permettre best response à la FP), et qu'on calcule en meme temps que vaut cette moyenne en jouant la politique de base.

===

peut-être que ça ressemble à Follow the Perturbed Leader?
http://dept.stat.lsa.umich.edu/~tewaria/research/abernethy16perturbation.pdf

https://arxiv.org/abs/2002.08676 learning with perturbed optimizers

algo qui utilise du sampling pour FP :
https://sci-hub.do/10.1109/tac.2017.2709548

https://arxiv.org/pdf/1903.09569.pdf
Monte Carlo Neural Fictitious Self-Play:Approach to Approximate Nash Equilibrium ofImperfect-Information Games

---

Explication :
$\pi_{\theta} : \mathbb{S} \times \mathbb{R^d} \rightarrow \mathbb{A}$
Dans le cas d'un problème à un unique état, $|\mathbb{S}|=1$, la politique prend en entrée un bruit.

Soit $\pi_{opt}$ la politique Nash sur le jeu d'intérêt.
Notre but : $\mathbb{E}_{z\sim\mathbb{P_{bruit}}} (\pi_{\theta}(z)) = \pi_{opt}$
ou alors $z\sim\mathbb{P_{bruit}} \implies \pi_{\theta}(z,.) \sim \pi_{opt}(.)$ (il y a plusieurs notions de convergence ?)

L'algorithme (v1, self-play) :
- Pour i de 1 à nbIters
- $z_1, z_2 \sim \mathbb{P}_{bruit}$
- $\pi_1 = \pi_{\theta}(z_1)$, $\pi_2 = \pi_{\theta}(z_2)$
- $obs = R \pi_2$
- $L = -<\pi_1, obs>$, où obs est considéré comme un vecteur constant.
- faire un pas de gradient de L selon $\theta$.

---
Puisque ça marche aussi sans bruit,
détaillons l'intuition pour cela aussi.

$\pi^{(1)}_{moy}$ observe $R \pi^{(2)}_{moy}$ et fait un pas dans la direction de $\nabla_{\pi}\pi^T R \pi^{(2)}_{moy} [\pi^{(1)}_{moy}]$.

Question : est-il réaliste d'observer $R \pi^{(2)}_{moy}$ ?
Remarque : ne marche pas en maintenant les moyennes, mais marche très bien comme cela.

Intuition : on joue avec la politique moyenne, on regarde par où la déplacer légèrement pour aller vers la best_response. C'est un peu comme si on travaillait directement sur l'équation $\pi_{moy,t+1} = (1-\alpha)\pi_{moy,t} + \alpha \pi_{br}$ de fictitious play. Cette équation correspond en effet à un pas de gradient.

Remarque : cet algorithme revient à considérer des politiques qui ignorent le bruit en entrée. On peut donc penser que si on joue contre une politique qui suit un algorithme différent, la politique avec un bruit peut théoriquement faire "au moins aussi bien".

marque avec adagrad.
le papier d'adagrad : https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf

https://arxiv.org/pdf/1308.4049.pdf

proche de l'idée de paramétrer par un bruit :
https://arxiv.org/pdf/1911.11928.pdf

papier qui ressemble à ce que je fais :
https://arxiv.org/pdf/1903.05614.pdf

et la suite : https://proceedings.icml.cc/paper/2020/file/b837305e43f7e535a1506fc263eee3ed-Paper.

smoothing de nesterov : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.322.5275&rep=rep1&type=pdf

if multiagents learning is the answer, what is the question:
http://robotics.stanford.edu/users/shoham/www%20papers/LearningInMAS.pdf

# Pourquoi le sampling ne marche pas pour les best-responses

On pourrait penser que la best response à la moyenne du passé est la best response à une des actions du passé.

Voici un exemple qui montre que c'est faux :
$A = Re_{1} = (50, -60, 1) \implies Br(A) = 0$
$B = Re_{2} = (-60, 50, 1) \implies Br(B) = 1$
$C = \frac{1}{2} R(e_{1} + e_{2}) = (-5, -5, 1) \implies Br(C) = 2$.

Cet exemple a lui seul justifie que pour la première moyenne, il faut :
- soit jouer contre la politique moyenne de l'adversaire
- soit sampler plusieurs des observations du passé (approximation du point 1)
- soit faire le KL-trick (approximation du point 1)

===

pseudo-codes :
regularized FP

entrée : R (mais on n'a besoin que de $R \pi_{adv}$ à chaque tour)

- initialiser $\pi_0$.
- initialiser $v=0$.
- pour chaque tour t
- initialiser $\pi_t = \pi_{t-1}$.
- mettre à jour $v = R \pi_{t-1}$
- résoudre $\pi_t = argmax <\pi_t, v> - \lambda KL(\pi_t, \pi_{t-1})$
- mettre à jour $\pi_{moy} = \frac{1}{t+1} \pi_t + \frac{t}{t+1} \pi_{moy}$

sortie : $\pi_{moy}$

gradient-based FP

- initialiser $\pi_{\theta}$
- pour chaque tour t
- calculers $probs, logits = \pi_{\theta}()$
- calculer $obs := R\,probs$
- calculer $L := - logits^T obs$ où $obs$ est gardé constant par rapport à $\theta$.
- $\theta = \theta - \lambda \nabla_{\theta} L$

noised-based FP

- initialiser $\pi_{\theta}$
- pour chaque tour t
- calculer $noise \sim N(0,1)$
- calculer $probs, logits = \pi_{\theta}(noise)$
- calculer $obs := R\,probs$
- calculer $L := - logits^T obs$ où $obs$ est gardé constant par rapport à $\theta$.
- $\theta = \theta - \lambda \nabla_{\theta} L$

bootstrapping gradient with regret matching

- initialiser $\pi_{\theta}$
- pour chaque tour t
- calculers $probs, logits = \pi_{\theta}()$
- calculer $obs_{j2} := -probs^T R$
- calculer $positiveAdv := ReLU(obs_{j2} - obs_{j2}^T probs + \epsilon)$
- calculer $estimate\_{\pi_2} := \frac{positiveAdv}{\sum positiveAdv}$
- calculer $obs := R \pi_2$
- calculer $L := - probs^T obs$ où $obs$ est gardé constant par rapport à $\theta$.
- $\theta = \theta - \lambda \nabla_{\theta} L$

https://proceedings.neurips.cc/paper/2020/hash/f1cf2a082126bf02de0b307778ce73a7-Abstract.html

https://science.sciencemag.org/content/365/6456/885

==

un papier qui essaie d'apprendre la stratégie de l'autre joueur par du bayesianisme : https://poker.cs.ualberta.ca/publications/AAAI05.pdf

pas compris ce papier mais ils approximent l'exploitability: https://ala2020.vub.ac.be/papers/ALA2020_paper_43.pdf

Domaine intéressant : https://en.wikipedia.org/wiki/Bayesian_game
Où il faut inférer des croyances sur l'adversaire (par ex sa fonction de reward, sont état caché...)