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:
- 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.
- 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.
- 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.
- 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.
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