Algorithm based on Blackwell's approachability theory used for regret minimization in strategic games
Explore the docs »
View Demo
·
Report Bug
·
Request Feature
Table of Contents
Blackwell proved in An analog of the minimax theorem for vector payoffs, (1965), the existence of a “no-regret” algorithm for a wide class of simple online learning problems involving multi-objective optimization. In the project, we implement such an algorithm making use of the celebrated Blackwell Approachability Theorem for two-player games with player's regrets as vector quantities. More specifically, at each round, players deploy mixed strategies that are derived from the stationary distribution of the regret matrices. This procedure verifies Blackwell condition and allows players' regrets to approach the negative orthant, thus minimizing them. This method guarantees that the empirical distributions of play converge to the set of correlated equilibria of the stage game. For more details, see A Simple Adaptive Procedure Leading to Correlated Equilibrium (2000), Hart & Mas-Colell.
Python 3.9
The following python packages are needed to run the program
These can all be installed with pip, e.g.,
pip install nashpy
Run the command: python3 BlackwellStrategy.py
Any contributions you make are greatly appreciated.
- Fork the Project
- Create your Feature Branch (
git checkout -b feature/NewFeature
) - Commit your Changes (
git commit -m 'Add some NewFeature'
) - Push to the Branch (
git push origin feature/NewFeature
) - Open a Pull Request
Distributed under the MIT License. See LICENSE
for more information.
Omar BOUFOUS
Link to Website: https://omarboufous.me
Mail: contact@omarboufous.me
Project Link: https://github.com/oboufous/Blackwell-Strategy