Safety Constrained Multi-Agent Reinforcement Learning for Active Voltage Control

Yang Qu, Jinming Ma, Feng Wu, Siddhartha Banerjee, Éva Tardos

TL;DR

This paper tackles the challenge of fairly allocating a shared resource among competing agents without using money. They introduce a novel randomized bidding strategy that significantly improves the guaranteed utility for each agent, pushing it from a long-standing 50% to approximately 59% of their ideal share, even when other agents behave adversarially. This work nearly closes the gap to the theoretical maximum achievable guarantee.

What Problem Does This Paper Address?

Imagine a scenario where multiple users (e.g., research labs) need to share a single, valuable resource (like a supercomputing cluster) over time. The resource can only be used by one user at any given moment, and there's no monetary system to facilitate allocation. The goal is to ensure "fairness," meaning each user gets a reasonable share of the resource's benefit, proportional to their "fair share" (e.g., a larger lab might have a larger fair share). This fairness must be "robust," meaning it holds even if other users act selfishly or even maliciously to gain an advantage.

For years, the best known robust guarantee was that each agent could secure at least 50% of their "ideal utility" (the maximum they could get if they had exclusive access to their fair share of the resource). This 50% bound was achieved through various mechanisms, but improving it proved difficult. This paper aims to break this 50% barrier and find a better robust guarantee for online resource sharing.

Methods

The authors work within the framework of a repeated first-price auction using artificial currency, a mechanism previously studied for this problem. Their core innovation is a Randomized Robust Bidding (RRB) strategy. Instead of bidding a fixed amount when they have a high value for the resource, agents now bid a value drawn from a uniform distribution. Specifically, if an agent's current value for the resource falls within the top $\alpha$-quantile of their value distribution (where $\alpha$ is their fair share), they draw their bid from a uniform distribution over a specific range.

A key theoretical contribution is a reduction that shows the problem of achieving robust guarantees for any value distribution can be simplified to the case where values are drawn from a Bernoulli distribution. This allows them to focus their analysis on this specific, simpler distribution. They also employ a two-player zero-sum game formulation to analyze the interaction between an agent and a combined adversary representing all other agents.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulations rather than empirical evaluation on real-world datasets.

Key Insights and Ideas

  • Randomization is Key: The paper demonstrates that introducing randomness into bidding strategies is crucial for improving robust utility guarantees beyond the 50% mark. Fixed bidding strategies are inherently predictable and exploitable by adversaries.
  • Uniform Distribution Power: The specific choice of a uniform distribution for bidding is not arbitrary. It's shown to be optimal in a certain sense for minimizing spending while maximizing the chance of winning, especially when combined with careful optimization of the bid range.
  • Bernoulli Distribution as Worst-Case: The reduction to Bernoulli distributions is significant because it establishes this distribution as the "worst-case" scenario for agents trying to achieve high robust guarantees. This simplifies theoretical analysis and provides a strong foundation for lower bounds.
  • Almost Tight Bounds: The paper not only provides a new strategy with a better guarantee but also shows that this guarantee is nearly optimal, with theoretical upper bounds closely matching their proposed strategy's performance.

Key Results

  • Improved Robust Guarantee: The proposed Randomized Robust Bidding (RRB) strategy guarantees each agent approximately a $2 - \sqrt{2} \approx 0.59$ fraction of their ideal utility, a significant improvement over the previous 0.5 guarantee. This holds robustly against any behavior from other agents.
  • Near Optimal: The authors show that any static (budget-independent) bidding policy can guarantee at most a 0.6 fraction of ideal utility, and they also provide a strategy for an adversary that limits an agent's utility to approximately $1 - 1/e \approx 0.63$. This suggests their $0.59$ guarantee is very close to the theoretical limit.
  • Empirical Validation: Simulations show that when all agents use the RRB strategy, their achieved utility approaches the theoretical maximum of $1 - (1 - 1/n)^n$, which tends to 1 as the number of agents ($n$) increases. This is significantly better than the 0.5 achieved by deterministic strategies.

Limitations and Future Work

  • Assumptions: The analysis relies on assumptions like agents having time-invariant value distributions and the pseudo-market mechanism. The robustness of the RRB strategy against more complex adversarial behaviors or different mechanisms might require further investigation.
  • Complexity of Proofs: While the RRB strategy is described as simple, the theoretical proofs for the bounds are complex, involving martingale analysis and intricate mathematical derivations.
  • Future Work: The authors suggest that their work on closing the gap between upper and lower bounds for robust resource sharing is ongoing. They also point to the potential interest in the adversary's bidding distribution they derive, which could be useful for further research in this area. The empirical results also suggest that the RRB strategy can outperform its theoretical worst-case guarantee in practice, hinting at further avenues for exploration.

Summary updated

BibTeX
@inproceedings{qu2024safety,
  author = {Yang Qu and Jinming Ma and Feng Wu and Siddhartha Banerjee and Éva Tardos},
  title = {{Safety Constrained Multi-Agent Reinforcement Learning for Active Voltage Control}},
  booktitle = {AIforCI @ IJCAI},
  year = {2024},
  url = {https://openreview.net/forum?id=I2KKVDUvHP},
}
Figure