Multi-Agent Stage-wise Conservative Linear Bandits

1. Problem Formulation

The paper addresses the Stochastic Linear Bandit problem within a Multi-Agent Networked Setting under Stage-wise Conservative Constraints.

• Setting: A network of $N$ agents operates over $T$ rounds on an undirected connected graph $G=(V, E)$. Agents communicate only with immediate neighbors.
• Objective: The agents collaboratively aim to maximize the global cumulative reward, defined by the average of local unknown parameters: $\theta^*_{global} = \frac{1}{N}\sum_{i=1}^N \theta^*_i$.
• Local Observation: At each round $t$, an agent $i$ observes a local reward $r^i_t = x_t^\top \theta^*_i + \eta^i_t$, where $x_t$ is the chosen action and $\eta^i_t$ is sub-Gaussian noise.
• Conservative Constraint: Unlike standard bandits, agents must satisfy a safety constraint at every single round. The expected reward of the chosen action must be no less than $(1-\alpha)$ times the expected reward of a known baseline policy ($r_{b,t}$):
  $$x_t^\top \theta^*_{global} \geq (1-\alpha)r_{b,t}$$
  where $\alpha \in (0,1)$ is the conservatism parameter. This prevents catastrophic failures (e.g., recommending a product the user will hate).
• Communication Cost: Communication between agents is not free; every communication round incurs additional regret because the network must continue playing the same action while exchanging information.

2. Methodology: MA-SCLUCB

The authors propose MA-SCLUCB (Multi-Agent Stage-wise Conservative Linear UCB), an episodic algorithm that balances exploration, exploitation, safety, and consensus.

A. Episodic Structure

Time is divided into episodes $s=1, 2, \dots$. Each episode consists of two phases:

1. Exploration-Exploitation Phase: The network selects a single action $x_{t_s}$ based on current estimates. All agents play this action and observe local rewards.
2. Communication Phase: Agents perform $q(s)$ rounds of communication to reach consensus on the average reward. During these $q(s)$ rounds, agents continue playing the same action $x_{t_s}$ to maintain consistency, incurring regret but gaining information.

B. Accelerated Consensus Protocol

To minimize communication overhead, the algorithm uses an Accelerated Consensus protocol (Algorithm 1) based on the spectral properties of the network weight matrix $W$.

• The number of communication rounds per episode is set to $q(s) = \lceil \log(2Ns) / \sqrt{2\log(1/|\lambda_2|)} \rceil$, where $|\lambda_2|$ is the second largest eigenvalue magnitude of $W$.
• This schedule ensures that the consensus error (difference between local estimate and global average) decays as $O(1/s)$.

C. Estimation and Confidence Regions

• Estimator: Each agent maintains a Regularized Least Squares (RLS) estimate of $\theta^*_{global}$ using the consensus-averaged rewards.
• Confidence Ellipsoid: Agents construct a confidence set $\mathcal{E}^i_s$ around their estimate. The confidence radius $\beta_s$ accounts for both observation noise (reduced by factor $1/\sqrt{N}$) and consensus approximation errors.

D. Action Selection Strategy

At the start of an episode, the selected agent chooses an action based on the Optimism in the Face of Uncertainty (OFU) principle, constrained by safety:

1. Estimated Safe Set: The agent constructs a set of actions guaranteed to be safe for all parameters within the confidence region:
   $$\mathcal{X}^{safe, i}_s = \{x \in \mathcal{X} : x^\top \hat{\theta}^i_{global} - \beta_s \|x\|_{\Sigma^{-1}} \geq (1-\alpha)r_{b,t}\}$$
2. UCB Selection: If the safe set is non-empty and sufficient exploration has occurred (verified by the minimum eigenvalue of the Gram matrix), the agent selects the action maximizing the upper confidence bound within the safe set.
3. Conservative Fallback: If the safe set is empty or exploration is insufficient, the agent plays a conservative action:
   $$x^{cons}_t = (1-\rho)x_{b,t} + \rho \zeta_t$$
   where $x_{b,t}$ is the baseline action and $\zeta_t$ is a random exploration vector. This ensures safety while promoting exploration in all directions.

3. Key Contributions & Theoretical Results

A. Regret Bound

The paper proves that MA-SCLUCB achieves a high-probability regret bound of:
$$\tilde{O}\left( \frac{d}{\sqrt{N}} \sqrt{T} \cdot \left( 1 + \frac{\log(NT)}{\sqrt{\log(1/|\lambda_2|)}} \right) \right)$$
where $d$ is the dimension and $T$ is the horizon.

B. Three Key Insights

1. Network Advantage ($1/\sqrt{N}$): Despite local communication, collaboration provides a fundamental statistical advantage. Averaging $N$ agents' observations reduces variance, improving the regret scaling from $O(\sqrt{T})$ (single agent) to $O(\sqrt{T/N})$.
2. Communication Price (Logarithmic): The cost of consensus grows only logarithmically with time and network size ($\log(NT)$). For well-connected networks (small $|\lambda_2|$), this overhead is negligible compared to the statistical gain.
3. Safety is Cheap: The stage-wise safety constraint adds only a lower-order regret term. The algorithm guarantees safety at every step without fundamentally altering the $\sqrt{T}$ scaling rate.

4. Experimental Validation

The authors validated the theory using synthetic linear bandit problems ($d=2, T=20,000$):

• Connectivity: Experiments on $k$-regular graphs showed that higher connectivity (larger $k$, smaller $|\lambda_2|$) leads to faster convergence and lower cumulative regret, confirming the theoretical dependence on network topology.
• Safety Compliance: The expected reward consistently remained above the safety threshold $(1-\alpha)r_{b,t}$ across all configurations.
• Scaling: Parameter estimation error decreased as $N$ increased, validating the $1/\sqrt{N}$ improvement.
• Conservatism: Higher $\alpha$ (stricter safety) resulted in higher regret and slower convergence, as the algorithm was forced to play conservative actions longer.

5. Significance

This work is significant because it bridges the gap between distributed learning and safety-critical decision making.

• Real-world Applicability: It addresses scenarios like recommendation systems or autonomous control where agents must collaborate to learn optimal policies but cannot afford "exploration failures" that violate safety constraints at any single step.
• Efficiency: It demonstrates that distributed learning with safety guarantees can achieve near-optimal performance even with restricted local communication, provided the network is reasonably connected.
• Theoretical Foundation: It provides the first rigorous analysis of stage-wise conservative constraints in a multi-agent linear bandit setting, proving that safety does not preclude efficient distributed learning.