# Probe-then-Commit Multi-Objective Bandits: Theoretical Benefits of Limited Multi-Arm Feedback

arXiv: https://arxiv.org/abs/2602.03175 · HTML: https://mlsanity.com/paper/2602.03175/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 3 Feb 2026.

## Builds on (most cited first, 6 of 6)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Mobile Edge Computing: A Survey on Architecture and Computation Offloading](https://mlsanity.com/paper/1702.05309/) (2017)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Provably Efficient Multi-Objective Bandit Algorithms under Preference-Centric Customization](https://mlsanity.com/paper/2502.13457/) (2025)

## Abstract (arXiv)

We study an online resource-selection problem motivated by multi-radio access selection and mobile edge computing offloading. In each round, an agent chooses among K candidate links/servers (arms) whose performance is a stochastic d-dimensional vector (e.g., throughput, latency, energy, reliability). The key interaction is probe-then-commit (PtC): the agent may probe up to q>1 candidates via control-plane measurements to observe their vector outcomes, but must execute exactly one candidate in the data plane. This limited multi-arm feedback regime strictly interpolates between classical bandits (q=1) and full-information experts (q=K), yet existing multi-objective learning theory largely focuses on these extremes. We develop textscPtC-P-UCB, an optimistic probe-then-commit algorithm whose technical core is frontier-aware probing under uncertainty in a Pareto mode, e.g., it selects the q probes by approximately maximizing a hypervolume-inspired frontier-coverage potential and commits by marginal hypervolume gain to directly expand the attained Pareto region. We prove a dominated-hypervolume frontier error of tildeO (KP d/√qT), where KP is the Pareto-frontier size and T is the horizon, and scalarized regret tildeO (Lφ d√(K/q)T), where φ is the scalarizer. These quantify a transparent 1/√q acceleration from limited probing. We further extend to multi-modal probing: each probe returns M modalities (e.g., CSI, queue, compute telemetry), and uncertainty fusion yields variance-adaptive versions of the above bounds via an effective noise scale.