# Game Redesign in No-regret Game Playing

arXiv: https://arxiv.org/abs/2110.11763 · HTML: https://mlsanity.com/paper/2110.11763/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 31 references that are in the map.
- First posted on arXiv 18 Oct 2021.

## Builds on (most cited first, 13 of 13)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Adaptive Reward-Poisoning Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12613/) (2020)
- [Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning](https://mlsanity.com/paper/2003.12909/) (2020)
- [Policy Poisoning in Batch Reinforcement Learning and Control](https://mlsanity.com/paper/1910.05821/) (2019)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Adversarial Attacks on Stochastic Bandits](https://mlsanity.com/paper/1810.12188/) (2018)
- [Data Poisoning Attacks on Stochastic Bandits](https://mlsanity.com/paper/1905.06494/) (2019)
- [Deceptive Reinforcement Learning Under Adversarial Manipulations on Cost Signals](https://mlsanity.com/paper/1906.10571/) (2019)
- [Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamics](https://mlsanity.com/paper/2009.00774/) (2020)
- [Adversarial Attacks on Linear Contextual Bandits](https://mlsanity.com/paper/2002.03839/) (2020)
- [Robust Policy Gradient against Strong Data Corruption](https://mlsanity.com/paper/2102.05800/) (2021)
- [Data Poisoning Attacks in Contextual Bandits](https://mlsanity.com/paper/1808.05760/) (2018)
- [Robust Stochastic Bandit Algorithms under Probabilistic Unbounded Adversarial Attack](https://mlsanity.com/paper/2002.07214/) (2020)

## Built on by (most cited first, 8 of 8)

- [Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.01888/) (2022)
- [Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2307.07670/) (2023)
- [Adversarial Attacks on Adversarial Bandits](https://mlsanity.com/paper/2301.12595/) (2023)
- [Corruption-Robust Offline Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2403.07933/) (2024)
- [Minimally Modifying a Markov Game to Achieve Any Nash Equilibrium and Value](https://mlsanity.com/paper/2311.00582/) (2023)
- [Data Poisoning to Fake a Nash Equilibrium in Markov Games](https://mlsanity.com/paper/2306.08041/) (2023)
- [Optimally Installing Strict Equilibria](https://mlsanity.com/paper/2503.03676/) (2025)
- [When Can You Poison Rewards? A Tight Characterization of Reward Poisoning in Linear MDPs](https://mlsanity.com/paper/2604.10062/) (2026)

## Abstract (arXiv)

We study the game redesign problem in which an external designer has the ability to change the payoff function in each round, but incurs a design cost for deviating from the original game. The players apply no-regret learning algorithms to repeatedly play the changed games with limited feedback. The goals of the designer are to (i) incentivize all players to take a specific target action profile frequently; and (ii) incur small cumulative design cost. We present game redesign algorithms with the guarantee that the target action profile is played in T-o(T) rounds while incurring only o(T) cumulative design cost. Game redesign describes both positive and negative applications: a benevolent designer who incentivizes players to take a target action profile with better social welfare compared to the solution of the original game, or a malicious attacker whose target action profile benefits themselves but not the players. Simulations on four classic games confirm the effectiveness of our proposed redesign algorithms.