Piecewise-Stationary Multi-Objective Multi-Armed Bandit With Application to Joint Communications and Sensing

Amir Rezaei Balef, Setareh Maghsudi

Introduction

In the evolving landscape of wireless communications, particularly with the advent of 6G and autonomous systems, decision-making agents must navigate increasingly complex environments. Two primary challenges emerge: the necessity to optimize multiple conflicting objectives simultaneously—such as maximizing data rates while ensuring high radar detection probability—and the inherent non-stationarity of the physical world. This paper introduces a novel framework for the Piecewise-Stationary Multi-Objective Multi-Armed Bandit (MoMAB) problem, specifically tailored for Joint Communication and Sensing (JCAS) applications.

Problem Formulation

The classical Multi-Armed Bandit (MAB) paradigm involves an agent selecting from a set of "arms" to maximize a single reward. However, real-world engineering often demands a multi-objective approach where no single "best" arm exists. Instead, the goal is to identify the Pareto front—a set of optimal trade-offs where no objective can be improved without degrading another.

Furthermore, these environments are often piecewise-stationary. Unlike stationary environments where reward distributions are fixed, or continuously drifting environments, piecewise-stationary settings experience abrupt shifts at unknown time intervals (breakpoints). Existing MoMAB solutions typically assume stationarity or rely on "passive" adaptation techniques like sliding windows, which often suffer from slow convergence and high regret during transitions.

The Proposed Framework

The authors propose a two-layered algorithmic approach designed to handle both multi-dimensionality and abrupt environmental changes.

1. Pareto Generic UCB

For stable periods between breakpoints, the agent employs a Pareto Generic Upper Confidence Bound (UCB) algorithm. Rather than using "scalarization"—the process of collapsing multiple objectives into a single weighted sum—this algorithm operates directly within the multi-dimensional reward space. It utilizes a Kullback-Leibler (KL)-based UCB to estimate the Pareto front. By leveraging the specific distribution of rewards (specifically Bernoulli in this study), KL-UCB provides tighter confidence bounds and superior sample efficiency compared to standard UCB variants.

2. Active Change Detection

To address non-stationarity, the Pareto UCB is wrapped in a Restarted Bayesian Online Change-point Detector (RBOCD). This "active" mechanism monitors the reward streams for statistical deviations. Upon detecting a significant shift, the RBOCD triggers a "restart" of the UCB algorithm. This allows the agent to discard obsolete information and rapidly converge to the new Pareto front of the altered environment.

Theoretical Contributions

The paper provides a rigorous theoretical analysis of the proposed framework. The authors prove that their algorithm achieves a regret bound of $O(\gamma_T \log(T))$, where $\gamma_T$ represents the number of breakpoints. In scenarios where the number of breakpoints is known a priori, this bound can be further refined to $O(\gamma_T \log(T/\gamma_T))$. This demonstrates that the regret scales logarithmically with time and linearly with the number of environmental shifts, which is near-optimal for this class of problems.

Experimental Evaluation

The framework was validated across three distinct scenarios:

  1. JCAS Simulation: An agent optimizes transmission power in a JCAS system to balance Energy Efficiency (EE) for communication and Probability of Detection (PD) for radar.
  2. Synthetic Benchmarking: A controlled environment with 4 arms and 3 objectives subjected to 4 abrupt breakpoints to test tracking capabilities.
  3. Real-World Application (Yahoo! Webscope R6A): A large-scale dataset of 4.5 million news article clicks, adapted to a bi-objective problem (click-through rate vs. article durability) with 9 simulated breakpoints to reflect changing user interests.

Key Results

The proposed RBOCPD Pareto klUCB consistently outperformed state-of-the-art baselines, including Discounted and Sliding Window Pareto UCB. Cumulative regret curves revealed sharp "elbows" at breakpoints, indicating that the active change detection mechanism identifies shifts significantly faster than passive methods. Furthermore, the algorithm demonstrated higher accuracy in identifying arms on the true Pareto front compared to scalarization-based approaches.

Conclusion and Future Work

This research bridges the gap between multi-objective optimization and non-stationary reinforcement learning. By combining multi-dimensional KL-UCB with active Bayesian change detection, the authors provide a robust solution for dynamic engineering challenges like JCAS.

While the current work focuses on Bernoulli distributions and requires a minimum detectable gap between shifts to trigger the detector, it sets a strong foundation for future exploration. The authors suggest extending this framework to more complex JCAS problems, such as beamforming design or optimizing phase shifts in Reconfigurable Intelligent Surfaces (RIS), as well as exploring off-policy learning scenarios.

Summary updated

Abstract

We study a multi-objective multi-armed bandit problem in a dynamic environment. The problem portrays a decision-maker that sequentially selects an arm from a given set. If selected, each action produces a reward vector, where every element follows a piecewise-stationary Bernoulli distribution. The agent aims at choosing an arm among the Pareto optimal set of arms to minimize its regret. We propose a Pareto generic upper confidence bound (UCB)-based algorithm with change detection to solve this problem. By developing the essential inequalities for multi-dimensional spaces, we establish that our proposal guarantees a regret bound in the order of $\gamma _{T}\log (T/{\gamma _{T}})$ when the number of breakpoints $\gamma _{T}$ is known. Without this assumption, the regret bound of our algorithm is $\gamma _{T}\log (T)$ . Finally, we formulate an energy-efficient waveform design problem in an integrated communication and sensing system as a toy example. Numerical experiments on the toy example and synthetic and real-world datasets demonstrate the efficiency of our policy compared to the current methods.
BibTeX
@article{balef2023piecewise,
  author = {Amir Rezaei Balef and Setareh Maghsudi},
  title = {{Piecewise-Stationary Multi-Objective Multi-Armed Bandit With Application to Joint Communications and Sensing}},
  journal = {IEEE Wireless Communications Letters},
  year = {2023},
  doi = {10.1109/lwc.2023.3244686},
}
Figure