How Minimax Regret Optimization Tackles Black‑Box Adversarial Bidding Constraints

1. Introduction

Display advertising is a major online marketing channel where advertisers use programmatic bidding services provided by DSPs to meet ROI constraints. Recent work has shifted constrained bidding from feedback control to reinforcement‑learning‑based methods, but existing RL approaches assume independent and identically distributed (i.i.d.) training and test conditions, which is unrealistic in the competitive, adversarial ecosystem of external ad placements.

In external placement scenarios, multiple stakeholders—our advertiser, competing advertisers, and the media—engage in a game where each tries to maximize its own utility, often leading to conflicting objectives. Media may set personalized reserve prices or even learn auction mechanisms end‑to‑end, while competitors employ unknown bidding strategies that cause the cost distribution faced by our policy to change dynamically. This creates an adversarial environment that has received little research attention.

The paper targets the black‑box adversarial setting where the auction mechanism and competitors’ strategies are unknown, yet advertisers still care about ROI constraints. The problem is modeled as a game with a hidden adversary that can perturb the environment to degrade the performance of a non‑adaptive bidding policy.

2. Method

The focus is on ROI‑constrained bidding, which can represent many marketing goals. Following recent work, the authors adopt a reinforcement‑learning formulation but omit formal MDP details for brevity. Traditional RL‑based constrained bidding assumes the training environment distribution matches the test distribution.

Because external placement involves strategic interactions, the i.i.d. assumption fails and the environment becomes adversarial. Moreover, the black‑box nature of media mechanisms and competitor strategies provides no prior knowledge about the adversary.

2.1 Minimax Regret Optimization

In a strict adversarial setting, the opponent knows our policy and can choose the worst‑case environment. The authors assume the probability of a test environment is proportional to how poorly the policy performs in that environment, leading to an energy‑based distribution where regret serves as free energy and a temperature parameter controls adversarial strength.

Using KL‑divergence, they project the training distribution onto a subset of training environments, resulting in an entropy‑constrained regret‑minimization objective. The temperature hyper‑parameter interpolates between a fully adversarial regime (high regret, low temperature) and an i.i.d. regime (uniform distribution).

Optimizing this objective yields a two‑level Minimax Regret Optimization (MiRO) framework: the inner level finds a training distribution aligned with the potential test distribution, and the outer level improves the policy under that distribution. Compared with standard empirical risk minimization (ERM), MiRO provides a regret upper bound that improves robustness under adversarial conditions.

2.2 Differentiable Game

Solving the bi‑level MiRO problem directly is difficult. Inspired by differentiable games and GAN training, the authors transform the minimax problem into a differentiable game and apply dual ascent to find a solution.

Because the regret function is not directly differentiable with respect to the environment, they reconstruct a causal world model from offline bidding logs to obtain latent representations of adversarial factors. This enables two conveniences:

Search for training distributions within the learned latent space, replacing the unknown environment variable with its latent counterpart.

Map latent states to rewards, making the regret function differentiable and allowing gradient‑based optimization of the training distribution.

The world model consists of:

Representation model: maps decision trajectories to adversarial variables using a variational information bottleneck (VIB).

Observation model: predicts rewards.

Latent dynamics model: captures transitions in the latent space.

Training objectives for the representation model and observation model are expressed as explicit loss functions (shown in the original figures).

With the reconstructed world model, the original MiRO objective replaces the environment with its latent representation, yielding a differentiable game that alternates between a “teacher step” (selecting worst‑case training environments) and a “student step” (updating the policy on the selected distribution).

3. Experiments

The authors evaluate MiRO on both synthetic and real ad‑auction environments. Results show that MiRO consistently outperforms existing baselines under both adversarial and i.i.d. conditions, demonstrating superior robustness.

Ablation studies confirm the contribution of each component (entropy constraint, world model, teacher‑student alternation). Additional analyses explore the impact of different assumed media mechanisms.

4. Conclusion

To address constrained bidding in black‑box adversarial external placement, the paper proposes a Minimax Regret Optimization framework that aligns training and test distributions, builds a causal world model, and converts the bi‑level problem into a solvable differentiable game. Experiments on synthetic and real data validate its effectiveness.

References

[1] Alexey Drutsa. 2020. Reserve pricing in repeated second‑price auctions with strategic bidders. ICML.

[2] Paul Dütting et al. 2019. Optimal auctions through deep learning. ICML.

[3] Yanjun Han et al. 2020. Learning to bid optimally and efficiently in adversarial first‑price auctions. arXiv.

[4] Thomas Nedelec et al. 2021. Adversarial Learning in Revenue‑Maximizing Auctions. AAMAS.

[5] David Balduzzi et al. 2018. The mechanics of n‑player differentiable games. ICML.

[6] Alexander A. Alemi et al. 2016. Deep variational information bottleneck. arXiv.