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

Amir Rezaei Balef, Setareh Maghsudi

TL;DR

This paper introduces a novel framework for solving multi-objective multi-armed bandit (MoMAB) problems in dynamic, piecewise-stationary environments. By combining a Pareto-based upper confidence bound (UCB) algorithm with an online change-point detector, the proposed method achieves optimal regret bounds and significantly outperforms traditional windowing approaches. The practical utility of this framework is demonstrated through an energy-efficient waveform design problem in Joint Communication and Sensing (JCAS) systems.

What Problem Does This Paper Address?

In many real-world sequential decision-making scenarios, an agent must balance multiple conflicting objectives simultaneously. For instance, in wireless networks, a system might need to maximize data throughput while minimizing energy consumption. This is traditionally modeled as a Multi-Objective Multi-Armed Bandit (MoMAB) problem, where the goal is to find the "Pareto optimal" set of actions—actions where you cannot improve one objective without degrading another.

However, most existing MoMAB algorithms assume a stationary environment where reward distributions never change. In reality, environments are dynamic; channel qualities fluctuate, user preferences shift, and radar targets move. This paper tackles the piecewise-stationary MoMAB problem, where the underlying reward distributions remain constant for certain intervals but change abruptly at unknown time steps (breakpoints). The challenge is to quickly detect these changes and adapt the decision-making policy to minimize cumulative "Pareto regret."

Methods

The authors propose a two-layered algorithmic approach:

  1. Pareto Generic UCB (Algorithm 1): Designed for stationary multi-objective environments, this algorithm calculates an Upper Confidence Bound (UCB) vector for each arm using a strong semi-distance Kullback-Leibler (KL)-dominated function. It identifies non-dominated arms to construct an empirical Pareto front and samples uniformly from this optimal set.
  2. Change-Detection Wrapper (Algorithm 2): To handle non-stationarity, the authors integrate the Restarted Bayesian Online Change-point Detector (RBOCD). This wrapper continuously monitors the rewards. The moment it detects a statistical shift in the reward distribution, it completely resets the UCB policy, allowing it to clear its outdated memory and rapidly learn the new environment.

The authors also provide rigorous mathematical backing by extending Cramer-Chernoff inequalities to multi-dimensional spaces. They prove that if the number of breakpoints ($\gamma_T$) over a time horizon $T$ is known, the algorithm achieves a total regret bound of $O(\gamma_T \log(T/\gamma_T))$. If unknown, the bound is $O(\gamma_T \log T)$.

Datasets

The framework was evaluated using three distinct setups:

  • JCAS Toy Example: A simulated environment modeling transmission power adaptation in a joint automotive radar and communication system. The two conflicting objectives are Data Information Rate (DIR) and Probability of Detection (PD) over a time-varying Rayleigh fading channel.
  • Synthetic Dataset: A controlled environment featuring $K=4$ arms, $\gamma_T=4$ breakpoints, and $D=3$ objectives following piecewise-stationary Bernoulli distributions.
  • Real-World Dataset (Yahoo! Webscope R6A): A massive dataset containing over 45 million user visits to the Yahoo! Today module. The authors adapted this into a non-stationary bi-objective problem (balancing click-through rate and publisher payout) by isolating the 10 most durable articles and introducing artificial non-stationary segments.

Key Insights and Ideas

  • Active Detection vs. Passive Forgetting: Traditional methods for non-stationary environments rely on sliding windows or discount factors to slowly "forget" old data. This paper shows that actively detecting the exact moment a change occurs and resetting the model yields much sharper adaptation and lower overall regret.
  • Multi-Dimensional Concentration Bounds: Proving regret bounds for multi-objective bandits is notoriously difficult because rewards are vectors, not scalars. The authors successfully generalized classical single-dimension concentration inequalities (like Chernoff bounds) to multi-dimensional Pareto spaces, providing a blueprint for future theoretical work in MoMABs.

Key Results

The proposed method, RBOCPD Pareto klUCB, consistently outperformed state-of-the-art windowing and discounting baselines across all experiments:

  • JCAS Application: As shown in the performance plots, the proposed algorithm successfully converges to solutions that satisfy the minimum thresholds for both communication and sensing metrics, even after abrupt environmental changes.
Fig. 1: Comparison of regret and performances for the toy example. After some iterations, our proposed algorithm converges to the optimal solutions that satisfy the minimum desired requirements. That means that our algorithm is applicable in much practical communication as an online optimizer.
  • Synthetic Benchmarks: On the synthetic dataset, the cumulative Pareto regret of the proposed method flattens out significantly faster after each breakpoint compared to standard Pareto UCB algorithms, which continue to accumulate heavy regret.
Fig. 2: Comparison of regret performance using a synthetic dataset with K = 4 arms, γT = 4 breakpoints and D = 3 objectives.
  • Real-World Data: In the Yahoo! Webscope experiment, the proposed change-detection framework kept cumulative regret below 100 over a 100,000-step horizon, whereas standard stationary Pareto methods skyrocketed to over 600 regret due to their inability to adapt.
Fig. 3: Comparison of regret performance using the Yahoo! Webscope dataset with K = 10 arms, γT = 9 breakpoints, and D = 2 objectives. The mean rewards corresponding to 5 out of 10 articles appear in the figure.

Limitations and Future Work

While highly effective, the current framework assumes that the objectives are independent per arm. Additionally, the change detector requires careful tuning of the parameter $\delta$ to balance the trade-off between false alarms and detection delay.

For future work, the authors suggest extending this framework to more complex architectural problems in wireless communications, such as optimizing beamforming designs for JCAS or controlling phase shifts in Reconfigurable Intelligent Surfaces (RIS). They also note that adapting this framework for off-policy learning scenarios remains an open and promising direction.

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 $γ_T\log(T/{γ_T})$ when the number of breakpoints $γ_T$ is known. Without this assumption, the regret bound of our algorithm is $γ_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