Paper deep dive
Coverage-Maximizing Multinomial Subset Routing under Operational Constraints
Quan Zhou, Yiyan Huang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/23/2026, 1:56:22 AM
Summary
The paper introduces Multinomial Subset Routing (MSR), an online learning framework where a learner selects a subset of experts by sampling from a multinomial policy rather than choosing a deterministic subset. The reward is based on the best-performing expert in the subset (sum-max structure), and the system must satisfy long-term, two-sided operational constraints (covering and packing) under bandit feedback. The authors propose OMD-Approachability, an algorithm combining Online Mirror Descent with Blackwell's Approachability, achieving O(1/sqrt(T)) regret and constraint violation. The framework is validated on real-world crowdsourcing data.
Entities (8)
Relation Signals (7)
OMD-Approachability → combines → Online Mirror Descent
confidence 95% · We propose OMD-Approachability, combining online mirror descent with Blackwell's Approachability
OMD-Approachability → combines → Blackwell's Approachability
confidence 95% · We propose OMD-Approachability, combining online mirror descent with Blackwell's Approachability
Multinomial Subset Routing → uses → OMD-Approachability
confidence 95% · We propose OMD-Approachability... We ground the framework... and validate it empirically
Multinomial Subset Routing → optimizes → Sum-Max Reward
confidence 93% · The reward depends only on the best-performing expert(s) in the routed subset... yielding a sum-max structure
Multinomial Subset Routing → operatesunder → Bandit Feedback
confidence 92% · We require the selection to satisfy several long-term, two-sided operational constraints under bandit feedback
Multinomial Subset Routing → appliesto → Crowdsourcing
confidence 90% · validate it empirically on a real-world crowdsourcing dataset
Multinomial Subset Routing → appliesto → Medical Consultation
confidence 88% · We instantiate the general framework on three applications... Medical Consultation via Mixture-of-Expert LLMs
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We introduce Multinomial Subset Routing (MSR), a new online routing framework over $K$ experts in which the learner keeps a multinomial routing policy instead of a deterministic subset of experts. At each round, the learner samples $M$ experts i.i.d. from the multinomial policy, and the resulting set of distinct sampled experts forms the routed subset. The reward depends only on the best-performing expert(s) in the routed subset. This reward structure arises naturally in routing across specialized models but is not captured by standard combinatorial bandits or subset-selection methods, which optimize deterministic subsets and typically assume additive rewards. We require the selection to satisfy several long-term, two-sided operational constraints under bandit feedback, observing only the winner's reward each round. We propose OMD-Approachability, combining online mirror descent with Blackwell's Approachability, and prove it achieves $O(1/\sqrt{T})$ regret in both reward and constraint violation. We ground the framework in practical application domains and validate it empirically on a real-world crowdsourcing dataset.
Tags
Links
- Source: https://arxiv.org/abs/2608.16375v1
- Canonical: https://arxiv.org/abs/2608.16375v1
Trouble viewing inline? Open PDF directly →
Full Text
82,728 characters extracted from source content.
Expand or collapse full text
Coverage-Maximizing Multinomial Subset Routing under Operational Constraints Quan Zhou Affiliation: National University of Singapore Yiyan Huang Thanks: Corresponding author: huangyiyan@gbu.edu.cn Affiliation: The Great Bay University Abstract We introduce Multinomial Subset Routing (MSR), a new online routing framework over K experts in which the learner keeps a multinomial routing policy instead of a deterministic subset of experts. At each round, the learner samples M experts i.i.d. from the multinomial policy, and the resulting set of distinct sampled experts forms the routed subset. The reward depends only on the best-performing expert(s) in the routed subset. This reward structure arises naturally in routing across specialized models but is not captured by standard combinatorial bandits or subset-selection methods, which optimize deterministic subsets and typically assume additive rewards. We require the selection to satisfy several long-term, two-sided operational constraints under bandit feedback, observing only the winner’s reward each round. We propose OMD-Approachability, combining online mirror descent with Blackwell’s Approachability, and prove it achieves O(1/T)O(1/ T) regret in both reward and constraint violation. We ground the framework in practical application domains and validate it empirically on a real-world crowdsourcing dataset. 1 Introduction The rise of specialized large language models (LLMs) has enabled hospitals to deploy ensembles of expert models—each trained on a distinct clinical domain—to assist in patient diagnosis and treatment planning. At each patient visit, the platform must select a subset of these specialists to consult. For any consults, only the most knowledgeable model determines the quality of the response, and the contributions of less capable models are subsumed. This winner-takes-all structure stands in sharp contrast to standard combinatorial bandits 30, where the quality is the sum of contributions of selected specialists. A patient’s case typically spans multiple clinical dimensions (e.g., a cardiac complication, a kidney function issue, and a neurological symptom); for each dimension, only the most proficient selected specialist contributes, and the total reward aggregates these per-dimension maxima, yielding a sum-max structure 37. Formally, given a set of K experts and N medical dimensions, the reward of consulting a subset A⊆[K]A [K] takes the form r(A)=∑k=1Nmaxi∈AVk,i,r(A)= _k=1^N _i∈ AV_k,i, where Vk,i≥0V_k,i≥ 0 denotes the proficiency of specialist i on the k-th medical dimension. This captures a fundamental property of ensemble consultation: specialists are complementary rather than additive. Crucially, these specialist models are black-box: the platform observes only the aggregate reward r(A)r(A) after consultation, not individual model contributions, motivating the bandit feedback setting. Another key distinction between the proposed setting and standard combinatorial bandits is that the platform does not seek a deterministic subset. Beyond maximizing clinical coverage, the platform must also respect operational constraints: each medical specialty must be consulted sufficiently often to ensure broad coverage, while computational resources must be balanced across servers to ensure timely responses. Consequently, a fixed deterministic subset may fail to satisfy these operational requirements. Instead, the platform seeks a multinomial routing policy that generates different subsets over time, allowing aggregate routing decisions to achieve both high clinical coverage and operational feasibility. We call this setting Multinomial Subset Routing (MSR). In MSR, the learner maintains a routing distribution over the K experts and, in each round, forms a subset by sampling M experts independently from this distribution. The resulting subset consists of the distinct experts sampled in that round. Thus, the optimization object is a routing policy rather than a deterministic subset. This setting is important for three reasons. First, a fixed MSR policy provides a simple and stable mechanism for repeatedly generating subsets over a long horizon. Second, repeated execution of the same policy enables long-term operational constraints, such as capacity and fairness, to be enforced through average routing frequencies. Third, for sum-max rewards, the expected reward induced by a MSR policy is concave over the probability simplex 37, enabling the use of online convex optimization techniques. Despite their practical importance, existing methods fail to address this problem in its full generality. On one hand, sum-max submodular bandits (37) capture the coverage structure of ensemble selection but do not incorporate operational constraints. On the other hand, bandit algorithms with knapsack constraints (6) typically handle budget requirements but assume simple linear or modular reward functions, which fail to model the coverage synergies inherent in multi-expert consultation. In the LLM routing literature, Mixture-of-Experts (MoE) approaches (40) learn to gate over specialists but lack provable feasibility guarantees and do not account for long-term constraint satisfaction. Combining sum-max rewards with operational constraints poses two technical challenges. The sum-max reward structure differs from standard combinatorial bandits, and while its concave structure 37 enables online optimization of the reward, it simultaneously introduces a non-convexity in the operational constraints. We show that both challenges can be overcome by carefully exploiting this concave structure for the reward objective while introducing a surrogate constraint reformulation to restore tractability. In this paper, we propose a novel framework for sum-max submodular bandits with two-sided operational (covering and packing) constraints. Our main contributions are: • We formulate the problem of online subset selection with sum-max rewards and multiple operational constraints under bandit feedback, a setting not addressed by prior work. • We propose an Online Mirror Descent algorithm with Approachability constraints (OMD-Approachability) that achieves sublinear regret in both reward and constraint violation, with provable feasibility guarantees. • We extend the framework to the contextual setting, where the learner observes a context before acting. • We instantiate the framework on some real-world applications and validate empirically on a real dataset, demonstrating that OMD-Approachability achieves competitive reward while maintaining feasibility. 2 Related Works Mixture-of-Experts The Mixture-of-Experts (MoE) architecture, introduced by 29 and scaled to modern LLMs by 40, increases model capacity by routing each input token to a learned subset of expert sub-networks via a gating function, activating only a fraction of parameters per forward pass. The Switch Transformer 21 formalized the notion of expert capacity — a hard upper bound on the number of tokens routable to each expert — and introduced load-balancing losses to prevent token dropping or expert collapse. This capacity constraint is a direct motivation for our work: the problem of routing queries to experts under capacity limits is naturally modeled as a bandit problem with knapsack constraints. LLM Routing. While MoE routing operates at the token level within a single model, a related but distinct line of work considers routing at the system level — selecting which LLM among a pool of candidates to invoke for each incoming query, trading off response quality against inference cost. Early approaches learn a routing function offline — either by directly optimizing performance minus scaled cost (14; 13), or by training a supervised router with labels from all candidate models (41; 36; 15; 22) — an assumption that breaks at deployment where only the outcome of the chosen model is observed (bandit feedback). Recent work addresses this by framing routing as an online learning problem: 35 formulates it as a multi-armed bandit that balances accuracy and cost, while 46 uses a contextual bandit conditioned on a user-specified performance–cost preference vector. Our work differs along several dimensions: we route a subset of experts simultaneously rather than a single model, we operate under more restricted feedback (only the aggregated reward of the chosen subset is observed), and the selection is subject to multi-dimensional whole-horizon covering and packing constraints. These constraints generalize the single cost-budget of prior work and can additionally encode operational limits (e.g., query caps on a specific GPU cluster) or fairness requirements (e.g., guaranteeing each hospital receives a minimum allocation of queries). This routing-under-capacity problem above is closely related to the following Bandits with Knapsacks (BwK) (6). Bandits with Knapsacks. The framework, pioneered by 6, studies the problem of online decision-making under resource consumption constraints. Over the years, it has been extended in numerous directions, including contextual settings (42; 2), linear bandits (4), combinatorial variants (32; 38), and adversarial settings (28), as well as connections to dueling bandits (20). While the majority of approaches adopt UCB-style algorithms, recent work has explored Thompson sampling as an alternative (19). Most relevant to our work is the setting of concave rewards and convex knapsacks (3), which proposes to handle the constraints via Blackwell’s Approachability algorithm; our work builds on and extends this line of research. Submodular Maximization with Constraints. This line of work dates back to the last century, studying the problem of selecting a subset that maximizes a submodular set function subject to combinatorial constraints (5). It is relevant to our setting because the sum-max reward function we consider is also submodular, satisfying the diminishing-returns property. Classical approaches include greedy (34), double greedy (9), and local search (31), with a celebrated breakthrough being the continuous greedy algorithm (10), which achieves the optimal (1−1/e)(1-1/e) approximation for monotone submodular maximization under a matroid constraint, with extensions to non-monotone cases (8). More recent works extend this framework to richer settings, including the intersection of matroid and knapsack constraints (39; 7), changing environments (48; 33), online settings (26; 43) and resource-aware settings (47). However, These methods all require access to a value oracle of the set function, or with a access to subroutine to draw samples to estimate the function value e.g., (24), that remain inapplicable to our setting, where the reward function is unknown and must be learned from observations on the fly. Submodular Bandits. This line of work relaxes the assumption of full access to a value oracle. The earliest works (50; 49) model the reward as a weighted sum of basis submodular functions with unknown weights, while still requiring access to the value oracle of each basis function. (49) additionally introduce a per-round knapsack constraint, meaning the budget is enforced independently at each round; in contrast, our whole-horizon knapsack couples decisions across rounds, requiring the algorithm to jointly manage exploration and resource consumption over time. (44) removes access to the value oracle entirely, requiring only marginal gain observations r(S∪i)−r(S)r(S∪\i\)-r(S), and extends to per-round knapsack and matroid constraints. (12) adopts the same observation model but additionally assumes marginal gains are representable via a kernel function. K-max Bandits. A special case is when the reward is the maximum over selected arms, which is itself submodular. Two distinct settings have been studied under the name K-max bandits: Extreme Bandits (18; 11; 1), which maximizes the expected best single-sample reward across T rounds, and (25; 23; 17), which defines the per-round reward as the maximum outcome within a selected subset — the setting directly related to ours, which we extend by incorporating knapsack constraints on action costs. The consideration of action costs is not entirely new (24; 37) that both treat costs as a shared quantity across actions. Our formulation is more general along two dimensions: first, we support multiple cost types simultaneously, where each cost type aggregates individual action costs over a specific group — motivated by the notion of expert capacity in Mixture-of-Experts (MoE) models; second, we support both upper-bound and lower-bound constraints on each cost type, requiring that certain resource consumption levels are met as well as not exceeded. We encode all of these as whole-horizon knapsack constraints. Combinatorial Bandits consider a decision maker that selects M base arms from K in each round, forming a super-arm (30). In the standard setting, the reward of a super-arm is determined by the rewards of its selected base arms, often through an additive structure. Popular methods include CUCB (16) and CTS (45). These methods typically select a deterministic super-arm, e.g., the top-M base arms according to their UCB or Thompson-sampling values. In contrast, MSR optimizes a multinomial routing policy that induces subsets through repeated sampling. 3 Motivating Examples We instantiate the general framework on three applications that illustrate the breadth of the coverage-maximizing bandit setting. Medical Consultation via Mixture-of-Expert LLMs. A hospital network operates K specialist LLMs, each trained on distinct datasets. At each patient visit, the platform selects a subset At⊆[K]A_t [K] of up to M specialists and receives a scalar reward rt(At)=∑k=1Nmaxi∈AtVk,i(t)r_t(A_t)= _k=1^N _i∈ A_tV^(t)_k,i, reflecting the clinical coverage of the consultation. Here Vk,i(t)≥0V^(t)_k,i≥ 0 captures how well specialist i covers clinical dimension k for patient t. Patient feedback reflects the quality of the consultation as a whole, not the contribution of any individual specialist, so only the aggregate reward rt(At)r_t(A_t) is revealed after consultation. As examples of the operational constraints this can capture: (i) a specialty coverage constraint, requiring each specialist to be consulted often enough that it keeps receiving cases to update on; and (i) a GPU load-balancing constraint, capping the average activations per server cluster. Crowdsourcing Team Formation. A crowdsourcing platform assembles teams of up to M workers from a pool of K to complete sequentially arriving projects. The team quality reward for the t-th project is rt(At)=∑k=1Nmaxi∈AtVk,i(t)r_t(A_t)= _k=1^N _i∈ A_tV^(t)_k,i, where Vk,i(t)V^(t)_k,i is the match quality between worker i and project t along skill dimension k (e.g. software development, graphic design). The project requester only rates the completed project as a whole, not each worker’s individual sub-contribution, so only the aggregate reward rt(At)r_t(A_t) is revealed after project completion. As examples of the operational constraints this can capture: (i) a wage budget constraint, capping the average spend per project; and (i) a group fairness constraint, requiring each demographic group to be hired sufficiently often on average. Online Ad Allocation. A platform selects a subset of up to M candidate ads to display at each of T rounds. The resulting engagement reward at the t-th round is rt(At)=∑k=1Nmaxi∈AtVk,i(t)r_t(A_t)= _k=1^N _i∈ A_tV_k,i^(t), where Vk,i(t)≥0V_k,i^(t)≥ 0 is the relevance of ad i to user-interest category k. The realized payoff (e.g. total session revenue) is logged for the displayed slate as a whole; ad-serving logs do not reliably attribute a single conversion to one specific ad among several shown together, so only the aggregate reward rt(At)r_t(A_t) is revealed after each round. As examples of the operational constraints this can capture: (i) a budget constraint, capping average spend per round; (i) a fairness constraint, requiring each advertiser group to receive a sufficient share of impressions on average; and (i) a load-balancing constraint, capping average activations per ad-serving node. 4 Problem Setup and Notation We consider an online learning problem in which a learner repeatedly selects subsets of actions to maximize cumulative reward while satisfying long-term operational constraints. Let K,M,T∈ℕK,M,T be fixed, where K denotes the number of available actions (specialists), M is the maximum number of actions selected per round, and T is the time horizon. We write [K]:=1,…,K[K]:=\1,…,K\ and denote by ΔK:=q∈ℝ+K:∑i=1Kqi=1 _K:= \q ^K_+: _i=1^Kq_i=1 \ the probability simplex over [K][K]. For u∈ℝdu ^d and a nonempty closed set A⊆ℝdA ^d, we write dist(u,A):=minx∈A‖x−u‖dist(u,A):= _x∈ A\|x-u\| for the Euclidean distance from u to A. Rewards and costs. Each round t is associated with a reward set function rt:2[K]→[0,1]r_t:2^[K]→[0,1] and rt(∅)=0r_t( )=0. Each action i∈[K]i∈[K] incurs a known cost vector ci∈[0,c¯]dc_i∈[0, c]^d, where c¯ c is the upper bound for each entry of the cost vector. Interaction protocol. The interaction protocol below formalizes the MSR setting introduced in Section 1. Nature fixes in advance a sequence of reward functions rtt=1T\r_t\_t=1^T, which remain hidden from the learner. At each round t=1,…,Tt=1,…,T, the learner proceeds as follows: 1. Choose a routing policy qt∈ΔKq_t∈ _K. 2. Draw M i.i.d. actions at,1,…,at,M∼qta_t,1,…,a_t,M q_t and form the (random) subset At:=at,j:j∈[M]⊆[K]A_t:=\a_t,j:j∈[M]\ [K], so |At|≤M|A_t|≤ M. 3. Observe the bandit feedback rt(At)r_t(A_t). 4. Incur the (random) loss ℓt:=∑i=1Kci 1[i∈At] _t:= _i=1^Kc_i\;1[i∈ A_t]. The learner must ensure the time-averaged loss vector lies within an axis-aligned box Sori=∏j=1d[lj,uj]S^ori= _j=1^d[l_j,u_j], i.e., 1T∑t=1Tℓt∈Sori 1T _t=1^T _t∈ S^ori. We assume throughout that 0≤uj≤Mc¯0≤ u_j≤ M c and 0≤lj≤c¯0≤ l_j≤ c. This is without loss of generality: coordinates violating the bounds are satisfied by every policy, since ci∈[0,c¯]dc_i∈[0, c]^d for i∈[K]i∈[K] and qt∈ΔKq_t∈ _K for t∈[T]t∈[T]. 4.1 Sum-Max Reward Functions Recall the informal sum-max reward r(S)=∑k=1Nmaxi∈SVk,ir(S)= _k=1^N _i∈ SV_k,i from Section 1; following 37, we now fix this formally. Definition 1 (Sum-max function). A set function r:2[K]→ℝr:2^[K] is sum-max if there exist N∈ℕN and a matrix V∈ℝN×KV ^N× K such that r(A)=∑k=1Nmaxi∈AVk,i∀A⊆[K],A≠∅,andr(∅)=0.r(A)= _k=1^N _i∈ AV_k,i ∀\,A [K],\;A≠ , r( )=0. Definition 2 (Expected reward). For any q∈ΔKq∈ _K, let b1(q),…,bM(q)b_1(q),…,b_M(q) be i.i.d. draws from the routing policy q and set B(q):=bj(q):j∈[M]B(q):=\b_j(q):j∈[M]\. For a set function r:2[K]→ℝr:2^[K] , define Φr(q):=[r(B(q))],q∈ΔK. ^r(q):=E[r(B(q))], q∈ _K. Lemma 1 (Concavity and gradient of Φr ^r). Let r be a sum-max function. Then Φr ^r is concave over ΔK _K, and for every q∈ΔKq∈ _K, the partial derivative of the expected reward with respect to the ithi^th entry qiq_i, is ∂iΦr(q)=[r(B(q))qi∑j∈[M]bj(q)=i]. _i ^r(q)=E [ r(B(q))q_i _j∈[M]1\b_j(q)=i\ ]. Proof. Both claims follow directly from 37: concavity of Φr ^r over ΔK _K follows from Theorem 2.3, and the gradient expression from Lemma 6.7. ∎ 4.2 Tractability and constraint reformulation Since the realized loss is stochastic, we analyze its expectation. At round t, under routing policy qt∈ΔKq_t∈ _K, arm i appears in AtA_t with probability 1−(1−qt,i)M1-(1-q_t,i)^M, so the expected cost vector is [ℓt]=∑i=1K(1−(1−qt,i)M)ci.E[ _t]\;=\; _i=1^K (1-(1-q_t,i)^M )\,c_i. (1) Recall that one of the learner’s goals is to keep the time-averaged observed cost inside a target set SoriS^ori. Since the realized loss ℓt _t is stochastic, we might first work with the constraint in expectation: 1T∑t=1T[ℓt]∈Sori 1T _t=1^TE[ _t]∈ S^ori. However, the map qt↦[ℓt]q_t [ _t] is concave for M≥1M≥ 1, which prevents the direct use of online convex optimization methods. To restore tractability and apply the approachability algorithm in (27), we construct a convex and compact set S such that playing qtq_t with ∑i=1Kqt,ici∈S _i=1^Kq_t,i\,c_i∈ S is sufficient to guarantee [ℓt]∈SoriE[ _t]∈ S^ori, i.e. S is a safe inner approximation of SoriS^ori under the linear surrogate. Let ci(j)c_i^(j) denote the jthj^th entry of the cost vector cic_i. The construction proceeds in two steps: (i) we replace [ℓt]E[ _t] by the linear surrogate ∑iqici _iq_ic_i, which yields a strict inner approximation; and (i) we truncate S to a box, which preserves both the feasible set and the constraint distance and serves only to render S compact, as the approachability analysis of Section 5 requires. (i) Surrogate substitution and rescaling. The map qt↦[ℓt]q_t [ _t] is concave, so constraining it directly does not yield a convex feasible set. We therefore constrain the linear surrogate ∑i=1Kqt,ici _i=1^Kq_t,ic_i instead, which is safe because the two are sandwiched coordinate-wise: for each j∈[d]j∈[d], ∑i=1Kqt,ici(j)≤[ℓt](j)≤M∑i=1Kqt,ici(j), _i=1^Kq_t,i\,c_i^(j)\;≤\;E[ _t]^(j)\;≤\;M _i=1^Kq_t,i\,c_i^(j), (2) by p≤1−(1−p)M≤Mp≤ 1-(1-p)^M≤ Mp for p∈[0,1]p∈[0,1], M≥1M≥ 1, together with ci(j)≥0c_i^(j)≥ 0. Consequently it suffices to enforce ∑i=1Kqt,ici(j)≤uj/M _i=1^Kq_t,ic_i^(j)≤ u_j/M for an upper-bound coordinate, and ∑i=1Kqt,ici(j)≥lj _i=1^Kq_t,ic_i^(j)≥ l_j for a lower-bound one11 1 Note that since q↦[ℓt](j)=∑i(1−(1−qi)M)ci(j)q [ _t]^(j)= _i(1-(1-q_i)^M)c_i^(j) is concave, the constraint [ℓt](j)≥ljE[ _t]^(j)≥ l_j is convex in q and can be enforced directly without any surrogate. This yields a tighter benchmark OPTOPT, at the cost of non-linear constraints in (6); we adopt the linear surrogate on both sides for uniformity of exposition.. (i) Truncating S to a box. The half-lines produced by step (i) are unbounded, so the approachability assumption defined in later text is violated. Since ∑iqici(j)∈[0,c¯] _iq_ic_i^(j)∈[0, c] for every q∈ΔKq∈ _K and j∈[d]j∈[d], we may intersect each S(j)S^(j) with [0,c¯][0, c] and take S(j)=[ 0,uj/M](upper-bound coordinates),S(j)=[lj,c¯](lower-bound coordinates),S^(j)=[\,0,\ u_j/M\,] (upper-bound coordinates), S^(j)=[\,l_j,\ c\,] (lower-bound coordinates), so that S=∏jS(j)⊆[0,c¯]dS= _jS^(j) [0, c]^d. This alters neither the feasible set defined in step (i) nor the value of dist(∑iqici,S)dist( _iq_ic_i,S), but renders S compact. The following lemma is the guarantee of this construction. Recall that Sori=∏j=1d(Sori)(j)S^ori= _j=1^d(S^ori)^(j) is a product of intervals, where each coordinate j is either an upper-bound coordinate with (Sori)(j)=(−∞,uj](S^ori)^(j)=(-∞,u_j], or a lower-bound coordinate with (Sori)(j)=[lj,∞)(S^ori)^(j)=[l_j,∞); the corresponding coordinates of S are S(j)=[0,uj/M]S^(j)=[0,u_j/M] and S(j)=[lj,c¯]S^(j)=[l_j, c]. Lemma 2 (Distance transfer). For any sequence q1,…,qT∈ΔKq_1,…,q_T∈ _K, define ϕ:=1T∑t=1T[ℓt]=1T∑t=1T∑i=1K(1−(1−qt,i)M)ci,φ:=1T∑t=1T∑i=1Kqt,ici.φ\;:=\; 1T _t=1^TE[ _t]\;=\; 1T _t=1^T _i=1^K (1-(1-q_t,i)^M )c_i, \;:=\; 1T _t=1^T _i=1^Kq_t,i\,c_i. Then dist(ϕ,Sori)≤M⋅dist(φ,S).dist\! (φ,\;S^ori )\;≤\;M·dist\! ( ,\;S ). Proof. Since SoriS^ori and S are both axis-aligned boxes, it suffices to show, for each coordinate j separately, dist(ϕ(j),(Sori)(j))≤M⋅dist(φ(j),S(j)).dist\! (φ^(j),\,(S^ori)^(j) )\;≤\;M·dist\! ( ^(j),\,S^(j) ). We handle the two cases in turn. Case 1: Upper-bound coordinate, (Sori)(j)=(−∞,uj](S^ori)^(j)=(-∞,u_j], S(j)=[0,uj/M]S^(j)=[0,u_j/M]. The distance of a scalar w≥0w≥ 0 from (−∞,u](-∞,u] is max(w−u,0) (w-u,0), and from [0,u/M][0,u/M] it is likewise max(w−u/M,0) (w-u/M,0). From the sandwich (2), applied coordinate-wise and averaged over t, 0≤ϕ(j)≤Mφ(j),0\;≤\;φ^(j)\;≤\;M ^(j), and in particular φ(j)≥0 ^(j)≥ 0. Therefore dist(ϕ(j),(Sori)(j)) (φ^(j),(S^ori)^(j) ) =max(ϕ(j)−uj, 0) = (φ^(j)-u_j,\,0) ≤max(Mφ(j)−uj, 0) ≤ (M ^(j)-u_j,\,0) =M⋅max(φ(j)−ujM, 0) =M· ( ^(j)- u_jM,\,0 ) =M⋅dist(φ(j),S(j)). =M·dist ( ^(j),S^(j) ). Case 2: Lower-bound coordinate, (Sori)(j)=[lj,∞)(S^ori)^(j)=[l_j,∞), S(j)=[lj,c¯]S^(j)=[l_j, c]. Since φ(j)≤c¯ ^(j)≤ c, the upper end of S(j)S^(j) is inactive and the distance of φ(j) ^(j) from S(j)S^(j) is max(lj−φ(j),0) (l_j- ^(j),0), as it is from [lj,∞)[l_j,∞). From the sandwich (2), averaged over t, ϕ(j)≥φ(j)≥0φ^(j)≥ ^(j)≥ 0, whence dist(ϕ(j),(Sori)(j))=max(lj−ϕ(j), 0)≤max(lj−φ(j), 0)=dist(φ(j),S(j)).dist (φ^(j),(S^ori)^(j) )= (l_j-φ^(j),\,0)\;≤\; (l_j- ^(j),\,0)=dist ( ^(j),S^(j) ). ∎ Corollary 1 (Constraint transfer). If 1T∑t=1T∑i=1Kqt,ici∈S 1T _t=1^T _i=1^Kq_t,i\,c_i∈ S, then 1T∑t=1T[ℓt]∈Sori 1T _t=1^TE[ _t]∈ S^ori. Proof. φ∈S ∈ S implies dist(φ,S)=0dist( ,S)=0, so Lemma 2 gives dist(ϕ,Sori)=0dist(φ,S^ori)=0, i.e. ϕ∈Sφ∈ S. ∎ 4.3 Online Learning Goal The learner’s goal is to simultaneously maximize the cumulative expected reward and keep the time-averaged observed cost inside a target set Sori⊆ℝdS^ori ^d. Since the realized loss ℓt _t is stochastic, we may impose the constraint in expectation: 1T∑t=1T[ℓt]∈Sori 1T _t=1^TE[ _t]∈ S^ori. The non-trivial interaction between the sum-max reward structure and the box constraints prevents a direct formulation. We therefore work with the linear surrogate constraint 1T∑t=1T∑iqt,ici∈S 1T _t=1^T _iq_t,ic_i∈ S in place of 1T∑t=1T[ℓt]∈Sori 1T _t=1^TE[ _t]∈ S^ori, which by Corollary 1 is sufficient to guarantee feasibility with respect to SoriS^ori. Further, we compare with the best fixed feasible routing policy in hindsight, not the best fixed subset. The benchmark is OPT:=maxq∈ΔK1T∑t=1TΦrt(q)s.t.∑i=1Kqici∈S.OPT:= _q∈ _K\; 1T _t=1^T ^r_t(q) .t. _i=1^Kq_i\,c_i\;∈\;S. (3) Since S is a convex polytope and the objective is concave in q (by Lemma 6.7 of 37), this is a concave program over a convex feasible set. We measure performance through two regret quantities. Objective regret. The first compares the learner’s cumulative expected reward against the benchmark OPTOPT, i.e. against the best fixed feasible routing policy in hindsight: ℛ1(T):=OPT−1T∑t=1TΦrt(qt).R_1(T):=OPT- 1T _t=1^T ^r_t(q_t). (4) Constraint regret. The second measures how far the learner ends up from feasibility. Note that it is stated in terms of the realized costs ℓt=∑i[i∈At]ci _t= _i1[i∈ A_t]c_i and the original target set SoriS^ori: ℛ2(T):=dist(1T∑t=1Tℓt,Sori).R_2(T):=dist\! ( 1T _t=1^T _t,\;S^ori ). (5) 5 Algorithm and Theoretical Guarantees We present Algorithm 1, where hS(w)=maxx∈Sw⊤xh_S(w)= _x∈ S\w x\ denotes the support function of S. Since S=∏j=1dS(j)S= _j=1^dS^(j) is a compact axis-aligned box, the support function hS(w)=maxx∈Sw⊤xh_S(w)= _x∈ S\w x\ is finite and decomposes coordinate-wise: h[0,uj/M](wj)=(uj/M)wjwj≥0,0wj<0,h[lj,c¯](wj)=c¯wjwj≥0,ljwjwj<0.h_[0,\,u_j/M](w_j)= cases(u_j/M)\,w_j&w_j≥ 0,\\[2.0pt] 0&w_j<0, cases h_[l_j,\, c](w_j)= cases c\,w_j&w_j≥ 0,\\[2.0pt] l_jw_j&w_j<0. cases By 37, gt,ig_t,i is an unbiased estimate of ∇Φrt(qt)∇ ^r_t(q_t), but may explode if qt,iq_t,i is too small. The following assumption prevents this. Assumption 1. The benchmark problem (3) is feasible and admits an optimal solution q∈ΔKq∈ _K satisfying qi≥γq_i≥γ for all i∈[K]i∈[K]. Remark 1 (feasibility of the QP). Assumption 1 implies that the quadratic program (6) is feasible. Let q⋆q be an optimal solution of the benchmark problem (3). By feasibility of (3), we have ∑i=1Kqi⋆ci∈S _i=1^Kq_i c_i∈ S. Hence, by Lemma 4, w⊤∑i=1Kqi⋆ci−hS(w)≤0,∀‖w‖≤1.w _i=1^Kq_i c_i-h_S(w)≤ 0, ∀\,\|w\|≤ 1. Since the dual iterate wtw_t, as defined in the algorithm, lies in the unit Euclidean ball, the above inequality holds for w=wtw=w_t. Moreover, Assumption 1 ensures that qi⋆≥γq_i ≥γ for all i. Therefore q⋆q satisfies both the linear constraint and the lower-bound constraints in (6), so q⋆q is a feasible point of the quadratic program. Consequently, QP (6) is feasible at every round. 1. Input: rescaled set S, OCO algorithm A, cost vectors ci∈[0,c¯]dc_i∈[0, c]^d for i∈[K]i∈[K], floor γ and learning rate η. 2. Set ⊂ℝdB ^d to be the unit Euclidean ball, as decision set for A. 3. Set q0,i:=1/Kq_0,i:=1/K and initialize g0,ig_0,i arbitrarily for i∈[K]i∈[K]. 4. For t=1,…,Tt=1,…,T: (a) Set ft−1(w):=w⊤(∑i=1Kqt−1,ici)−hS(w)f_t-1(w):=w ( _i=1^Kq_t-1,ic_i )-h_S(w). (b) Query A: wt←(f1,…,ft−1)w_t (f_1,…,f_t-1) (c) Set qtq_t as the solution of: maxq∈ΔK:q≥γq⊤gt−1−η2‖q−qt−1‖2s.t. wt⊤∑i=1Kqici−hS(wt)≤0 split _q∈ _K:\;q≥γ& q g_t-1- η2\|q-q_t-1\|^2\\ s.t. &w_t _i=1^Kq_i\;c_i-h_S(w_t)≤ 0 split (6) (d) Draw at,1,…,at,Ma_t,1,…,a_t,M independently from qtq_t; (e) Set At←at,j:j∈[M]A_t←\a_t,j:j∈[M]\; (f) Observe rt(At)r_t(A_t); (g) For each i∈[K]i∈[K], define gt,i←rt(At)qt,i∑j=1Mat,j=ig_t,i← r_t(A_t)q_t,i _j=1^MI\! \a_t,j=i \ Algorithm 1 Online Mirror Descent with Approachability Constraints 5.1 Theoretical Guarantees All proofs are deferred to Appendix. Theorem 1 (Reward regret). Let qtq_t for t∈[T]t∈[T] be the output of Algorithm 1 with proximal parameter η∗=2TKM(1γ+(M−1))η^*= 2TKM ( 1γ+(M-1) ). Then T[ℛ1(T)]≤22TKM(1γ+(M−1)).T\;E[R_1(T)]≤ 2 2TKM\! ( 1γ+(M-1) ). The constraint regret bound requires the following standard approachability condition. Theorem 2 (Constraint regret). Let A be an OCO algorithm with regret RegretT()Regret_T(A). Then for an absolute constant L>0L>0, [ℛ2(T)]≤M⋅RegretT()T+Mc¯Ldlog(2d)T.E [R_2(T) ]≤ M· Regret_T(A)T+M cL d (2d)T. Using online gradient descent (OGD) as A gives RegretT()=O(T)Regret_T(A)=O( T), so both regrets are O(1/T)O(1/ T) and thus sublinear. 5.2 Contextual extension We extend to the contextual setting, where at round t the learner observes a context xt∈x_t from a finite set X (e.g. the case type in Section 3) before selecting its routing policy. No distributional assumption is placed on the context sequence. The learner runs one independent copy of Algorithm 1 per context, sharing only the dual variable wtw_t across contexts to enforce the aggregate constraint. The contextual benchmark optimises over the best fixed feasible policy per context, OPTctx:=1T∑x∈maxq∈ΔK:qi≥γ∑iqici∈S∑t:xt=xΦrt(q),OPT^ctx:= 1T _x \; _ subarraycq∈ _K:\,q_i≥γ\\ _iq_ic_i∈ S subarray\; _t:\,x_t=x ^r_t(q), and the contextual regret is ℛ1ctx(T):=OPTctx−1T∑t=1TΦrt(qt(xt))R_1^ctx(T):=OPT^ctx- 1T _t=1^T ^r_t(q^(x_t)_t). The full contextual algorithm is given in Appendix D. Corollary 2 (Contextual reward regret). Run the contextual algorithm (Appendix D) with per-context anytime proximal parameter ηt=anxt _t=a n_x_t, where a=2KM(1γ+M−1)a=2 KM( 1γ+M-1) and nxtn_x_t is the visit count for context xtx_t up to round t. Then, without prior knowledge of T or T(x)\T^(x)\, T[ℛ1ctx(T)]≤ 4||TKM(1γ+(M−1)).T\,E\! [R_1^ctx(T) ]\;≤\;4 \,TKM\! ( 1γ+(M-1) ). The contextual regret is O(||)O( |X|) larger than the non-contextual bound—sublinear in the number of contexts. Remark 2 (Shared dual, decoupled primal). Algorithm 2 maintains a separate primal iterate q(x)q^(x) for each context x∈x , but a single shared dual variable wtw_t. At round t, only the primal iterate corresponding to the observed context xtx_t is updated, whereas wtw_t is updated using the policy actually played, qt=q(xt)q_t=q^(x_t). Consequently, the reward optimization decomposes into |||X| independent per-context online mirror descent problems, while the dual process couples all contexts through the aggregate surrogate cost 1T∑t=1T∑i=1Kqt,ici 1T _t=1^T _i=1^Kq_t,ic_i. Since the proof of Theorem 2 depends only on this aggregate surrogate cost sequence and the shared dual updates, it applies to Algorithm 2. Therefore the contextual algorithm satisfies the same constraint guarantee as in Theorem 2. 6 Numerical Experiments We complement the theoretical guarantees of Section 5.1 with a numerical study on the real-world TREC 2010 Crowdsourcing Track dataset. 6.1 Data and Preprocessing Source and cleaning. We use the TREC 2010 Crowdsourcing Track data distributed with the SpectralMethodsMeetEM repository of 51: trec_crowd.txt records each worker’s binary response to a task, and trec_truth.txt records each task’s gold label. Inner-joining the two on task ID (keeping only tasks with a recorded gold label) yields 677677 workers, 2,2752,275 tasks, and 12,86312,863 annotations. For each annotation we mark correct =response=gold label=1\response=gold label\, and define a worker’s overall accuracy as the mean of correct over their annotations. Workers with fewer than 55 annotations are discarded, since their accuracy estimate would otherwise be too noisy, leaving a reliable pool of 270270 workers. Per-seed worker pool. For each of the random seeds used throughout Section 6, K=50K=50 workers are sampled uniformly without replacement from the reliable pool. The skill and cost statistics below are recomputed within that sampled pool of 5050 workers, so quantities such as the cost normalization and the expert indicator are relative to the 5050 workers actually competing in that seed’s instance, not to the full reliable pool. Base skill matrix. The 2,2752,275 tasks are partitioned into N groups by round-robin index on the sorted task IDs (the j-th task in sorted order is assigned to group jmodNj N). The base skill matrix Vbase∈[0,1]N×50V_base∈[0,1]^N× 50 has Vbase[n,i]V_base[n,i] equal to sampled worker i’s accuracy restricted to group n’s tasks; if worker i has no annotations in group n, this entry is imputed with worker i’s overall accuracy. The value of N is specified per experiment. Cost matrix. Within the sampled pool of 5050, each worker i is assigned two cost coordinates: a workload cost, equal to i’s annotation count divided by the largest annotation count in the pool, taking values in [0,1][0,1]; and a binary expert indicator, equal to 11 for the 1010 highest-accuracy workers in the pool and 00 otherwise. Per-round realization V(t)V^(t). Since VbaseV_base is static, the per-round skill matrix V(t)V^(t) that forms the reward is instead drawn fresh each round from one of two environments built on top of VbaseV_base. In the stochastic environment, V(t)[n,i]∼Beta(κVbase[n,i],κ(1−Vbase[n,i]))V^(t)[n,i] (κ V_base[n,i],\,κ(1-V_base[n,i])) independently each round with concentration κ=20κ=20, modeling stationary per-round noise around each worker’s true accuracy. In the regime-switching environment, every T/10T/10 rounds a fresh random 10%10\% of workers (55 workers) have their mean accuracy shrunk by a factor of 0.20.2 for that block, modeling transient drops in annotator reliability (e.g. fatigue) that shift the optimal team composition over time before recovering at the next block. 6.2 Regret Convergence under Varying Constraint Tightness We verify that both the objective regret R1R_1 and the constraint regret R2R_2 decay at the O(n−1/2)O(n^-1/2) rate predicted by the theory, across two reward-dimension settings (N∈3,5N∈\3,5\) and three levels of constraint tightness (K=50K=50, M=5M=5, T=10,000T=10,000 rounds, 55 seeds, stochastic environment with κ=20κ=20). OMD-Approachability (Algorithm 1) is run in the batched setting where the routing distribution q is held fixed for B=10B=10 rounds and updated once per batch via a proximal QP step (6); the natural convergence clock is therefore the number of OMD update steps n=t/Bn=t/B, and all curves are plotted against n. Regret metrics. At each batch endpoint we compute two metrics. The objective regret R1(n)=1t∑s=1t(A∼qT[r(A,V(s))]−rs),t=nB,R_1(n)= 1t _s=1^t (E_A q_T[r(A,V^(s))]-r_s ), t=nB, where rs=rs(As)r_s=r_s(A_s) is the realized reward at round s. The quantity measures how much better the final learned policy qTq_T would have done if deployed from the start, relative to the algorithm’s actual trajectory. We use qTq_T as a proxy for the optimal feasible routing policy q∗q^* that attains OPTOPT (3), which is not available in closed form; after T=10,000T=10,000 rounds of learning, qTq_T is taken as its empirical surrogate. The expectation A∼qT[r(A,V(s))]E_A q_T[r(A,V^(s))] is estimated via 200200 Monte Carlo draws of A∼qTA q_T applied retrospectively to each V(s)V^(s). As t grows, the objective regret approaches zero, and the theoretical bound gives a rate of O(n−1/2)O(n^-1/2). The constraint regret R2(n)=dist(1t∑s=1tℓs,Sori)R_2(n)=dist\! ( 1t _s=1^t _s,\;S^ori ) is the Euclidean distance from the running-average realized cost vector to the original feasible box SoriS^ori; it is positive only when the time-averaged cost exceeds at least one constraint bound, and decays to zero once the algorithm stays consistently feasible. Constraint configurations. Table 1 lists the four configurations, varying the expert-cap bound αexpert _expert (maximum average number of top-accuracy workers selected per round) and the budget margin added to the baseline budget M⋅C0¯M· C_0. Table 1: Constraint configurations used in Sections 6.2 and 6.3. The “none” level (unconstrained) is used in Section 6.3 only. Config Budget margin Expert cap αexpert _expert tight (exp≤2≤ 2) +0.0+0.0 2.02.0 medium (exp≤2.5≤ 2.5) +0.1+0.1 2.52.5 loose (exp≤5≤ 5) +0.5+0.5 5.05.0 none (unconstr.) −- ∞ Hyperparameters. The OMD proximal parameter is η=ηmult2TKM(1/γ+M−1)η= _mult 2TKM(1/γ+M-1), with ηmult=0.03 _mult=0.03 for both N=3N=3 and N=5N=5. The dual OGD step size is ηogd=0.05 _ogd=0.05, and the exploration floor is γ=1/(10K)=0.002γ=1/(10K)=0.002. Figure and results. Figure 1 shows R1(n)R_1(n) (top row) and R2(n)R_2(n) (bottom row) for N=3N=3 (left) and N=5N=5 (right). On each panel a dashed c/nc/ n reference line is shown, reflecting the O(n−1/2)O(n^-1/2) theoretical prediction. For R1R_1, all three constraint configurations decay to near-zero by n=10,000n=10,000 under both N values. The empirical curves lie above the O(n−1/2)O(n^-1/2) reference throughout, indicating that convergence is initially slower than the reference rate; nevertheless all curves reach near-zero by the end of the horizon. A short warm-up plateau is visible at n≲30n 30, after which the curves enter a clear monotone descent. Under N=5N=5, the loose configuration shows a more pronounced early hump, reflecting the wider reward range of the higher-dimensional sum-max objective. For R2R_2, only the tight configuration registers meaningful constraint violation: the running-average cost vector starts above the expert-cap boundary, and the dual OGD corrections gradually steer selections away from over-used expert workers. The tight-configuration R2R_2 tracks the O(n−1/2)O(n^-1/2) reference closely, reaching approximately zero by n≈300n≈ 300 for N=3N=3 and n≈1,000n≈ 1,000 for N=5N=5; the larger and slower-decaying violation under N=5N=5 reflects the wider per-round cost variance when more skill groups are active. The medium configuration shows only a small initial transient that vanishes by n≈20n≈ 20–3030. The loose configuration remains at zero throughout. Figure 1: Objective regret R1(n)R_1(n) (top) and constraint regret R2(n)R_2(n) (bottom) vs. OMD update step n=t/10n=t/10, for N=3N=3 (left) and N=5N=5 (right). Mean ± one standard deviation across 55 seeds. Dashed line: O(n−1/2)O(n^-1/2) reference curve. 6.3 Crowdsourced Annotation via Worker Reliability We instantiate the crowdsourcing application of Section 3 on the worker pool and skill/cost matrices of Section 6.1, comparing eight policies across four constraint-tightness levels and two environment types. A team of M=5M=5 workers is selected per round over T=10,000T=10,000 rounds, with team-quality reward rt(At)=∑n=13maxi∈AtVn,i(t)r_t(A_t)= _n=1^3 _i∈ A_tV^(t)_n,i. Results are averaged over 2020 independent seeds. Constraint configurations. The same two knapsack constraints as Section 6.1 are used: a budget constraint bounding time-averaged workload, and an expert-cap constraint limiting the average number of top-accuracy workers selected per round. Four tightness levels are evaluated, as listed in Table 1. Policies. All UCB- and TS-based baselines begin with a round-robin warm-up of 1010 rounds that cycles through all K=50K=50 workers before switching to their learned selection rule. Because the sum-max reward is non-decomposable, these baselines attribute the full combinatorial reward rtr_t to each selected arm as a heuristic proxy for its individual contribution. • Random: selects M workers uniformly at random without replacement each round. No learning, no constraint awareness; lower-bound reference. • Greedy: after warm-up, always selects the M workers with the highest empirical mean (running average of the shared reward rtr_t). Pure exploitation; no exploration or constraint awareness. • CUCB (Combinatorial UCB): after warm-up, selects the top-M arms by UCB index μ^i+c2logt/ni μ_i+c 2 t/n_i, where μ^i μ_i is arm i’s empirical mean reward, nin_i is the number of rounds arm i has been selected so far, and c=2c=2. Since only the aggregate team reward rt(At)r_t(A_t) is observed, μ^i μ_i is updated via the shared-reward heuristic described above: rtr_t is attributed to every selected arm as a proxy for its individual contribution. No constraint awareness; serves as an unconstrained reward ceiling. • CBwK (Combinatorial Bandits with Knapsacks): extends CUCB with a Lagrangian dual ∈ℝ+d λ ^d_+, initialized at = λ=0. The selection score for arm i is UCBi+(⊙sign)⊤C:,iUCB_i+( λ ) C_:,i, steering away from constraint-violating arms as λ grows. Dual updated each round by subgradient ascent on the running-average constraint violation, step size 10/T10/ T. • TS (Thompson Sampling): maintains a Beta(αi,βi)Beta( _i, _i) posterior per arm, initialized at αi=βi=1 _i= _i=1. Each round samples si∼Beta(αi,βi)s_i ( _i, _i) and selects the top-M by sis_i. Posterior update: αi+=rt/N _i +=r_t/N, βi+=1−rt/N _i +=1-r_t/N for each selected arm (normalized by N to keep increments in [0,1][0,1]). No constraint awareness; Bayesian counterpart to CUCB. • TS-BwK (Thompson Sampling with Knapsacks): extends TS with the same Lagrangian dual as CBwK. Selection score is si+(⊙sign)⊤C:,is_i+( λ ) C_:,i; same subgradient dual update (step size 10/T10/ T). Bayesian counterpart to CBwK. • MoE (constrained online MoE gating): an adaptation of sparse Mixture-of-Experts gating (40) to the online, bandit-feedback, constrained setting. Each worker plays the role of an expert; the gating network is a logit vector ∈ℝK θ ^K that learns which experts to activate. Rather than training on a supervised loss with per-expert gradients, the gate is updated online via REINFORCE on the aggregate team reward — the only signal available under winner-only bandit feedback. Selection uses Gumbel-Top-M (top-M indices of + θ+ ξ, ξi∼i.i.d.Gumbel(0,1) _i i.i.d. Gumbel(0,1)), the standard stochastic routing mechanism of sparse MoE, which interpolates between uniform exploration and greedy exploitation as θ concentrates. Knapsack constraints are enforced via a Lagrangian dual λ, giving the update ←+ηlrreff(At−),reff=rt+(⊙sign)⊤xt,=softmax(),ηlr=0.01, θ← θ+ _lr\,r_eff\,(1_A_t-p), r_eff=r_t+( λ ) x_t, =softmax( θ), _lr=0.01, with λ initialized at 0 and updated by subgradient ascent at step size 4×10−44× 10^-4. • OMD-Approachability (proposed): Algorithm 1. Maintains a distribution q∈ΔKq∈ _K updated every B=10B=10 rounds via the constrained QP (6), using an importance-weighted bandit gradient with a running-average reward baseline. Arms are drawn M times with replacement from q; no per-arm decomposition is required. The dual wtw_t is updated each round via OGD on the unit ball. Primal proximal parameter η=ηmult2TKM(1/γ+M−1)η= _mult 2TKM(1/γ+M-1) with ηmult=0.05 _mult=0.05, dual step size ηogd=0.05 _ogd=0.05, exploration floor γ=1/(10K)=0.002γ=1/(10K)=0.002. Figures and results. Figure 2 reports the time-averaged reward and percentage of feasible runs across four constraint levels in both stochastic and regime-switching environments. Figure 3 shows the per-round rolling-average reward (window size 500500) under the tight and loose constraint settings for six representative policies. MoE and Random are omitted from Figure 3 because their substantially higher per-round variance dominates the plotting scale and obscures the comparison among the remaining methods. Reward–feasibility trade-off. The main result is that OMD-Approachability is the only policy that simultaneously achieves near-optimal reward and consistently satisfies the expert-cap constraint. Under the tight constraint, OMD-Approachability attains 100%100\% feasibility in both stochastic and regime-switching environments (Figure 2). In the stochastic environment, TS-BwK is also highly feasible (about 9595–100%100\%), whereas CBwK achieves only about 40%40\% feasibility. In the regime-switching environment, TS-BwK drops to about 85%85\%, while CBwK reaches about 65%65\%, indicating that the approachability-based controller is substantially more robust to non-stationarity than the Lagrangian dual baselines. Constraint-unaware policies (CUCB, TS, and Greedy) are rarely feasible under the tight constraint because they have no mechanism to regulate cumulative expert usage. Effect of constraint relaxation. As the constraint is relaxed from tight to medium, loose, and unconstrained, feasibility increases across all methods and reaches essentially 100%100\% under the loose and unconstrained settings (Figure 2). At the same time, the average rewards of OMD-Approachability, TS, Greedy, TS-BwK, and CUCB remain close to the maximum value of 3.03.0, while CBwK is consistently lower. Thus, OMD-Approachability preserves near-optimal reward without sacrificing feasibility, particularly in the constrained regimes where the differences between methods are most pronounced. Reward convergence dynamics. Figure 3 highlights the difference between constraint-aware and unconstrained policies. Under the tight constraint, TS and Greedy achieve the highest rewards because they do not enforce the expert-cap constraint and therefore serve as unconstrained upper baselines. Among the constraint-aware methods, OMD-Approachability initially sacrifices reward to regulate expert usage, but it steadily improves and converges to near-optimal reward by the end of the horizon. TS-BwK exhibits reward trajectories that are competitive with OMD-Approachability under the tight constraint, while CBwK converges more slowly and remains consistently below both methods. However, the reward curves must be interpreted together with the feasibility results in Figure 2. Although TS-BwK achieves comparable reward under the tight constraint, it satisfies the constraint in substantially fewer runs, especially in the regime-switching environment, whereas OMD-Approachability maintains 100%100\% feasibility. Thus, OMD-Approachability is the only constraint-aware policy that combines near-optimal reward with consistently reliable constraint satisfaction. The advantage of OMD-Approachability is particularly pronounced in the regime-switching environment. Under both tight and loose constraints, it achieves higher rolling reward than the other constraint-aware methods throughout most of the horizon while maintaining full feasibility. CBwK exhibits a persistent reward gap, and TS-BwK is more sensitive to non-stationarity, leading to lower reward and reduced feasibility under the tight constraint. Under the loose constraint, all methods approach similar reward levels, but OMD-Approachability remains the strongest performing constraint-aware policy. Figure 2: Constraint tightness sweep (K=50K=50, M=5M=5, N=3N=3, T=10,000T=10,000, 2020 seeds). Each row is an environment; columns show mean ± std of time-averaged reward (left) and % of seeds achieving feasibility (right). OMD-Approachability (blue) is the only policy that achieves 100%100\% feasibility under the tight constraint in both environments. Figure 3: Per-round rolling-average reward (window 5,0005,000) for tight (left) and loose (right) constraint configurations, across 2020 seeds (MoE and Random excluded due to high variance). Each row is an environment. Under tight constraint, OMD-Approachability (blue) starts lower than constraint-unaware baselines but converges to near-optimal reward while remaining feasible throughout. References [1] M. Achab, S. Clémençon, A. Garivier, A. Sabourin, and C. Vernade (2017) Max k-armed bandit: on the extremehunter algorithm and beyond. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, p. 389–404. Cited by: §2. [2] S. Agrawal, N. R. Devanur, and L. Li (2016) An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In Conference on Learning Theory, p. 4–18. Cited by: §2. [3] S. Agrawal and N. R. Devanur (2014) Bandits with concave rewards and convex knapsacks. In Proceedings of the fifteenth ACM conference on Economics and computation, p. 989–1006. Cited by: §2. [4] S. Agrawal and N. Devanur (2016) Linear contextual bandits with knapsacks. Advances in neural information processing systems 29. Cited by: §2. [5] F. Bach (2011) Learning with submodular functions: a convex optimization perspective. arXiv preprint arXiv:1111.6453. Cited by: §2. [6] A. Badanidiyuru, R. Kleinberg, and A. Slivkins (2018) Bandits with knapsacks. Journal of the ACM (JACM) 65 (3), p. 1–55. Cited by: §1, §2, §2. [7] A. Badanidiyuru and J. Vondrák (2014) Fast algorithms for maximizing submodular functions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, p. 1497–1514. Cited by: §2. [8] A. Bian, K. Levy, A. Krause, and J. M. Buhmann (2017) Continuous dr-submodular maximization: structure and algorithms. Advances in Neural Information Processing Systems 30. Cited by: §2. [9] N. Buchbinder, M. Feldman, J. Seffi, and R. Schwartz (2015) A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM Journal on Computing 44 (5), p. 1384–1402. Cited by: §2. [10] G. Calinescu, C. Chekuri, M. Pal, and J. Vondrák (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing 40 (6), p. 1740–1766. Cited by: §2. [11] A. Carpentier and M. Valko (2014) Extreme bandits. Advances in Neural Information Processing Systems 27. Cited by: §2. [12] L. Chen, A. Krause, and A. Karbasi (2017) Interactive submodular bandit. Advances in Neural Information Processing Systems 30. Cited by: §2. [13] L. Chen, M. Zaharia, and J. Y. Zou (2020) Frugalml: how to use ml prediction apis more accurately and cheaply. Advances in neural information processing systems 33, p. 10685–10696. Cited by: §2. [14] L. Chen, M. Zaharia, and J. Zou (2022) Efficient online ml api selection for multi-label classification tasks. In International conference on machine learning, p. 3716–3746. Cited by: §2. [15] S. Chen, W. Jiang, B. Lin, J. Kwok, and Y. Zhang (2024) Routerdc: query-based router by dual contrastive learning for assembling large language models. Advances in Neural Information Processing Systems 37, p. 66305–66328. Cited by: §2. [16] W. Chen, Y. Wang, Y. Yuan, and Q. Wang (2016) Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. Journal of Machine Learning Research 17 (50), p. 1–33. External Links: Link Cited by: §2. [17] Y. Chen, S. Wang, L. Huang, and W. Chen (2025) Continuous k-max bandits. arXiv preprint arXiv:2502.13467. Cited by: §2. [18] V. A. Cicirello and S. F. Smith (2005) The max k-armed bandit: a new model of exploration applied to search heuristic selection. In The Proceedings of the Twentieth National Conference on Artificial Intelligence, Vol. 3, p. 1355–1361. Cited by: §2. [19] R. Deb, M. Ghavamzadeh, and A. Banerjee (2025) Thompson sampling for constrained bandits. In Reinforcement Learning Conference, Cited by: §2. [20] R. Deb, A. Saha, and A. Banerjee (2024) Think before you duel: understanding complexities of preference learning under constrained resources. In International Conference on Artificial Intelligence and Statistics, p. 4546–4554. Cited by: §2. [21] W. Fedus, B. Zoph, and N. Shazeer (2022) Switch transformers: scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research 23 (120), p. 1–39. Cited by: §2. [22] T. Feng, Y. Shen, and J. You (2025) Graphrouter: a graph-based router for llm selections. In International Conference on Learning Representations, Vol. 2025, p. 26186–26203. Cited by: §2. [23] F. Fourati, C. J. Quinn, M. Alouini, and V. Aggarwal (2024) Combinatorial stochastic-greedy bandit. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 12052–12060. Cited by: §2. [24] A. Goel, S. Guha, and K. Munagala (2006) Asking the right questions: model-driven optimization using probes. In Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p. 203–212. Cited by: §2, §2. [25] A. Gopalan, S. Mannor, and Y. Mansour (2013) Thompson sampling for complex bandit problems. arXiv preprint arXiv:1311.0466. Cited by: §2. [26] N. Harvey, C. Liaw, and T. Soma (2020) Improved algorithms for online submodular maximization via first-order regret bounds. Advances in Neural Information Processing Systems 33, p. 123–133. Cited by: §2. [27] E. Hazan (2016) Introduction to online convex optimization. Foundations and Trends® in Optimization 2 (3-4), p. 157–325. External Links: Link, Document, ISSN 2167-3888 Cited by: Appendix A, Appendix C, §4.2. [28] N. Immorlica, K. Sankararaman, R. Schapire, and A. Slivkins (2022) Adversarial bandits with knapsacks. Journal of the ACM 69 (6), p. 1–47. Cited by: §2. [29] R. A. Jacobs, M. I. Jordan, S. J. Nowlan, and G. E. Hinton (1991) Adaptive mixtures of local experts. Neural computation 3 (1), p. 79–87. Cited by: §2. [30] B. Kveton, Z. Wen, A. Ashkan, and C. Szepesvari (2015) Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, p. 535–543. Cited by: §1, §2. [31] J. Lee, M. Sviridenko, and J. Vondrák (2010) Submodular maximization over multiple matroids via generalized exchange properties. Mathematics of Operations Research 35 (4), p. 795–806. Cited by: §2. [32] Q. Liu, W. Xu, S. Wang, and Z. Fang (2022) Combinatorial bandits with linear constraints: beyond knapsacks and fairness. Advances in Neural Information Processing Systems 35, p. 2997–3010. Cited by: §2. [33] T. Matsuoka, S. Ito, and N. Ohsaka (2021) Tracking regret bounds for online submodular optimization. In International Conference on Artificial Intelligence and Statistics, p. 3421–3429. Cited by: §2. [34] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher (1978) An analysis of approximations for maximizing submodular set functions—i. Mathematical programming 14 (1), p. 265–294. Cited by: §2. [35] Q. H. Nguyen, T. Dao, D. C. Hoang, J. Decugis, S. Manchanda, N. V. Chawla, and K. D. Doan (2024) Metallm: a high-performant and cost-efficient dynamic framework for wrapping llms. arXiv preprint arXiv:2407.10834. Cited by: §2. [36] I. Ong, A. Almahairi, V. Wu, W. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica (2024) Routellm: learning to route llms with preference data. arXiv preprint arXiv:2406.18665. Cited by: §2. [37] S. Pasteris, A. Rumi, F. Vitale, and N. Cesa-Bianchi (2023) Sum-max submodular bandits. arXiv preprint arXiv:2311.05975. Cited by: Appendix B, Appendix B, §1, §1, §1, §1, §2, §4.1, §4.1, §4.3, §5. [38] K. A. Sankararaman and A. Slivkins (2018) Combinatorial semi-bandits with knapsacks. In International Conference on Artificial Intelligence and Statistics, p. 1760–1770. Cited by: §2. [39] K. K. Sarpatwar, B. Schieber, and H. Shachnai (2019) Constrained submodular maximization via greedy local search. Operations Research Letters 47 (1), p. 1–6. Cited by: §2. [40] N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton, and J. Dean (2017) Outrageously large neural networks: the sparsely-gated mixture-of-experts layer. arXiv preprint arXiv:1701.06538. Cited by: §1, §2, 7th item. [41] T. Shnitzer, A. Ou, M. Silva, K. Soule, Y. Sun, J. Solomon, N. Thompson, and M. Yurochkin (2023) Large language model routing with benchmark datasets. arXiv preprint arXiv:2309.15789. Cited by: §2. [42] A. Slivkins, K. A. Sankararaman, and D. J. Foster (2023) Contextual bandits with packing and covering constraints: a modular lagrangian approach via regression. In The Thirty Sixth Annual Conference on Learning Theory, p. 4633–4656. Cited by: §2. [43] M. Streeter and D. Golovin (2008) An online algorithm for maximizing submodular functions. Advances in Neural Information Processing Systems 21. Cited by: §2. [44] S. Takemori, M. Sato, T. Sonoda, J. Singh, and T. Ohkuma (2020) Submodular bandit problem under multiple constraints. In Conference on Uncertainty in Artificial Intelligence, p. 191–200. Cited by: §2. [45] S. Wang and W. Chen (2018) Thompson sampling for combinatorial semi-bandits. In International Conference on Machine Learning, p. 5114–5122. Cited by: §2. [46] W. Wei, T. Yang, H. Chen, Y. Zhao, F. Dernoncourt, R. A. Rossi, and H. Eldardiry (2025) Learning to route llms from bandit feedback: one policy, many trade-offs. arXiv preprint arXiv:2510.07429. Cited by: §2. [47] Z. Xu, S. S. Garimella, and V. Tzoumas (2025) Communication-and computation-efficient distributed submodular optimization in robot mesh networks. IEEE Transactions on Robotics. Cited by: §2. [48] Z. Xu, H. Zhou, and V. Tzoumas (2023) Online submodular coordination with bounded tracking regret: theory, algorithm, and applications to multi-robot coordination. IEEE Robotics and Automation Letters 8 (4), p. 2261–2268. Cited by: §2. [49] B. Yu, M. Fang, and D. Tao (2016) Linear submodular bandits with a knapsack constraint. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 30. Cited by: §2. [50] Y. Yue and C. Guestrin (2011) Linear submodular bandits and their application to diversified retrieval. Advances in neural information processing systems 24. Cited by: §2. [51] Y. Zhang, X. Chen, D. Zhou, and M. I. Jordan (2016) Spectral methods meet em: a provably optimal algorithm for crowdsourcing. J. Mach. Learn. Res. 17 (1), p. 3537–3580. External Links: ISSN 1532-4435 Cited by: §6.1. Appendix Contents • Appendix A: Auxiliary Lemmas .A • Appendix B: Proof of Theorem 1 .B • Appendix C: Proof of Theorem 2 .C • Appendix D: Contextual Algorithm and Proof of Corollary 2 .D Appendix A Auxiliary Lemmas We collect here the supporting lemmas used across the proofs. Let wtw_t be defined in Algorithm 1. We also define the feasible regions used in the analysis: ℱ∘:=q∈ΔK:qi≥γ;∑iqici∈SF_ :=\q∈ _K:q_i≥γ;\; _iq_ic_i∈ S\ ℱτ:=q∈ΔK:qi≥γ;wt⊤∑iqici−hS(wt)≤0,∀t∈[τ],F_τ:=\q∈ _K:q_i≥γ;\;w_t _iq_ic_i-h_S(w_t)≤ 0,\;∀ t∈[τ]\, and their per-context analogues ℱ∘(x)F_ ^(x), ℱτ(x)F_τ^(x) with “∀t∈[τ]∀ t∈[τ]” replaced by “∀t∈[τ]:xt=x∀ t∈[τ]:x_t=x”. Note that ℱτF_τ and ℱτ(x)F_τ^(x) are random as wtw_t are randomly generated by the algorithm. For the measurability argument, define the filtration, i.e., the history before sampling AtA_t ℋt−1=σ(w1,…,wt,q1,…,qt,A1,r1(A1),…,At−1,rt−1(At−1)).H_t-1=σ\! (w_1,…,w_t,\;q_1,…,q_t,\;A_1,r_1(A_1),…,A_t-1,r_t-1(A_t-1) ). By construction of Algorithm 1, the variables qtq_t and wtw_t are ℋt−1H_t-1-measurable, while gtg_t is ℋtH_t-measurable. Lemma 3 (Three-point identity). For any q,qt,qt+1∈ℝKq,q_t,q_t+1 ^K, ⟨qt+1−qt,q−qt+1⟩=12‖q−qt‖2−12‖q−qt+1‖2−12‖qt+1−qt‖2. q_t+1-q_t,\,q-q_t+1 = 12\|q-q_t\|^2- 12\|q-q_t+1\|^2- 12\|q_t+1-q_t\|^2. Lemma 4. Let S be a convex and compact set, dist(u,S)=max‖w‖≤1w⊤u−hS(w).dist(u,S)= _\|w\|≤ 1 \w u-h_S(w) \. Proof. The proof follows Lemma 13.5 of [27]. Using the definition of the support function, max‖w‖≤1w⊤u−hS(w) _\|w\|≤ 1 \w u-h_S(w) \ =max‖w‖≤1w⊤u−max∈Sw⊤ = _\|w\|≤ 1 \w u- _x∈ Sw x \ =max‖w‖≤1min∈Sw⊤u−w⊤ = _\|w\|≤ 1 _x∈ S \w u-w x \ =min∈Smax‖w‖≤1w⊤u−w⊤(minimax theorem) = _x∈ S _\|w\|≤ 1 \w u-w x \ (minimax theorem) =min∈S‖−u‖ = _x∈ S\|x-u\| =dist(u,S). =dist(u,S). ∎ Appendix B Proof of Theorem 1 Proof of Theorem 1. Let q⋆∈argmax∑t=1Tq∈ℱ∘Φrt(q)q ∈ _q _ _t=1^T ^r_t(q). By the definition of OPTOPT in (3) and Assumption 1, ∑t=1TΦrt(q⋆)≥T⋅OPT. _t=1^T ^r_t(q )≥ T·OPT_. (7) Hence T⋅OPT−∑t=1TΦrt(qt)≤∑t=1T(Φrt(q⋆)−Φrt(qt)).T·OPT- _t=1^T ^r_t(q_t)≤ _t=1^T ( ^r_t(q )- ^r_t(q_t) ). (8) Step 1. By Lemma 4, for every realization of the algorithm, ℱ∘⊆ℱtF_ _t, because every wtw_t generated by Algorithm 1 satisfies ‖wt‖≤1\|w_t\|≤ 1. Therefore q⋆∈ℱtq _t almost surely for every t. Since qt+1q_t+1 is the solution of the proximal optimization problem (6), the first-order optimality condition gives ⟨gt−η(qt+1−qt),q−qt+1⟩≤0,∀q∈ℱt. g_t-η(q_t+1-q_t),\,q-q_t+1 ≤ 0, ∀ q _t. Applying this with q=q⋆q=q and using the three-point identity (Lemma 3), ⟨gt,q⋆−qt⟩≤η2(‖q⋆−qt‖2−‖q⋆−qt+1‖2−‖qt+1−qt‖2)+⟨gt,qt+1−qt⟩. g_t,q -q_t ≤ η2 (\|q -q_t\|^2-\|q -q_t+1\|^2-\|q_t+1-q_t\|^2 )+ g_t,q_t+1-q_t . By concavity of Φrt ^r_t, Φrt(q⋆)−Φrt(qt)≤⟨∇Φrt(qt),q⋆−qt⟩. ^r_t(q )- ^r_t(q_t)≤ ∇ ^r_t(q_t),\,q -q_t . Adding and subtracting gtg_t, Φrt(q⋆)−Φrt(qt) ^r_t(q )- ^r_t(q_t) ≤⟨gt,q⋆−qt⟩+⟨∇Φrt(qt)−gt,q⋆−qt⟩ ≤ g_t,q -q_t + ∇ ^r_t(q_t)-g_t,\,q -q_t ≤η2(‖q⋆−qt‖2−‖q⋆−qt+1‖2−‖qt+1−qt‖2) ≤ η2 (\|q -q_t\|^2-\|q -q_t+1\|^2-\|q_t+1-q_t\|^2 ) +⟨gt,qt+1−qt⟩+⟨∇Φrt(qt)−gt,q⋆−qt⟩. + g_t,q_t+1-q_t + ∇ ^r_t(q_t)-g_t,\,q -q_t . Summing over t=1,…,Tt=1,…,T and telescoping, ∑t=1T(Φrt(q⋆)−Φrt(qt)) _t=1^T ( ^r_t(q )- ^r_t(q_t) ) ≤η2‖q⋆−q1‖2+∑t=1T⟨gt,qt+1−qt⟩ ≤ η2\|q -q_1\|^2+ _t=1^T g_t,q_t+1-q_t (9) −η2∑t=1T∥qt+1−qt∥2 - η2 _t=1^T\|q_t+1-q_t\|^2 +∑t=1T⟨∇Φrt(qt)−gt,q⋆−qt⟩. + _t=1^T ∇ ^r_t(q_t)-g_t,\,q -q_t . Step 2. For the last term of (9), by Lemma 6.6 of [37], [gt∣ℋt−1]=∇Φrt(qt).E[g_t _t-1]=∇ ^r_t(q_t). Since both q⋆q and qtq_t are ℋt−1H_t-1-measurable, [⟨∇Φrt(qt)−gt,q⋆−qt⟩∣ℋt−1]=0.E\! [ ∇ ^r_t(q_t)-g_t,\,q -q_t _t-1 ]=0. Taking expectations and using the tower property, [∑t=1T⟨∇Φrt(qt)−gt,q⋆−qt⟩]=0.E\! [ _t=1^T ∇ ^r_t(q_t)-g_t,\,q -q_t ]=0. Step 3. For the first inner-product term of (9), Young’s inequality gives ⟨gt,qt+1−qt⟩≤2η‖gt‖2+η2‖qt+1−qt‖2. g_t,q_t+1-q_t ≤ 2η\|g_t\|^2+ η2\|q_t+1-q_t\|^2. Summing over i, the second term on the right-hand side exactly cancels the third term in (9). Again conditioning on ℋt−1H_t-1, Lemma 6.14 of [37] gives [gt,i2∣ℋt−1]≤Mqt,i+M(M−1).E[g_t,i^2 _t-1]≤ Mq_t,i+M(M-1). Since qt,i≥γq_t,i≥γ almost surely, [gt,i2∣ℋt−1]≤Mγ+M(M−1).E[g_t,i^2 _t-1]≤ Mγ+M(M-1). Taking expectations and summing over i, [‖gt‖2]=∑i=1K[gt,i2]≤KM(1γ+M−1).E[\|g_t\|^2]= _i=1^KE[g_t,i^2]≤ KM ( 1γ+M-1 ). Therefore ∑t=1T[‖gt‖2]≤TKM(1γ+M−1). _t=1^TE[\|g_t\|^2]≤ TKM ( 1γ+M-1 ). Step 4. Taking expectations on both sides of (8), and combining (9) with the bounds derived above, together with the Euclidean diameter bound of the simplex, ‖q⋆−q1‖2≤2\|q -q_1\|^2≤ 2, we obtain [T⋅OPT−∑t=1TΦrt(qt)] \! [T·OPT- _t=1^T ^r_t(q_t) ] ≤η+2η∑t=1T[‖gt‖2] ≤η+ 2η _t=1^TE[\|g_t\|^2] ≤η+2ηTKM(1γ+M−1). ≤η+ 2ηTKM ( 1γ+M-1 ). Step 5. Optimizing the upper bound over η gives η⋆=2TKM(1γ+M−1).η = 2TKM ( 1γ+M-1 ). Substituting this value yields [T⋅OPT−∑t=1TΦrt(qt)]≤22TKM(1γ+M−1),E\! [T·OPT- _t=1^T ^r_t(q_t) ]≤ 2 2TKM ( 1γ+M-1 ), which proves the theorem. ∎ Appendix C Proof of Theorem 2 The constraint regret could be decomposed as follows: ℛ2(T) _2(T) =dist(1T∑t=1Tℓt,Sori)=dist(1T∑t=1T∑i=1K[i∈At]ci,Sori) =dist\! ( 1T _t=1^T _t,\;S^ori )=dist\! ( 1T _t=1^T _i=1^K1[i∈ A_t]\,c_i,\;S^ori ) (10) ≤dist(1T∑t=1T∑i=1K[i∈At]ci,1T∑t=1T[ℓt])+dist(1T∑t=1T[ℓt],Sori) \! ( 1T _t=1^T _i=1^K1[i∈ A_t]\,c_i,\; 1T _t=1^TE[ _t] )+dist\! ( 1T _t=1^TE[ _t],\;S^ori ) ≤dist(1T∑t=1T∑i=1K[i∈At]ci,1T∑t=1T[ℓt])⏟sampling error+M⋅dist(1T∑t=1T∑i=1Kqt,ici,S)⏟approachability error, ≤ dist\! ( 1T _t=1^T _i=1^K1[i∈ A_t]\,c_i,\; 1T _t=1^TE[ _t] )_sampling error+M· dist\! ( 1T _t=1^T _i=1^Kq_t,i\,c_i,\;S )_approachability error, where the first inequality uses triangle inequality, the second inequality uses Lemma 2. Then, we deal with each term separately. Lemma 5 (Approachability error). Let qtq_t for t∈[T]t∈[T] be the output of Algorithm 1, with input OCO algorithm A. Then the average approachability error is dist(1T∑t=1T∑i=1Kqt,ici,S)≤RegretT()T.dist\! ( 1T _t=1^T _i=1^Kq_t,i\,c_i,\,S )\;≤\; Regret_T(A)T. Proof. The proof follows Theorem 13.7 of [27]. Set ut:=∑i=1Kqt,iciu_t:= _i=1^Kq_t,ic_i. Notice that qtq_t is the solution of the optimization problem (6), such that it satisfies its constraint, i.e., for wtw_t as defined in the algorithm, we have for any t, ft(wt)=wt⊤ut−hS(wt)≤0.f_t(w_t)=w_t u_t-h_S(w_t)≤ 0. (11) Set u¯T=1T∑t=1Tut u_T= 1T _t=1^Tu_t. Using Lemma 4, dist(u¯T,S) ( u_T,S) =max‖w‖≤1w⊤u¯T−hS(w) = _\|w\|≤ 1 \w u_T-h_S(w) \ =maxw∗∈1T∑t=1Tft(w∗)(definition of ft) = _w^* 1T _t=1^Tf_t(w^*) (definition of f_t) ≤1T∑t=1Tft(wt)+RegretT()T(OCO guarantee of ) ≤ 1T _t=1^Tf_t(w_t)+ Regret_T(A)T (OCO guarantee of A) ≤RegretT()T(Equation (11)). ≤ Regret_T(A)T (Equation~ equ:nonpositive-f). ∎ Lemma 6 (Sampling error). With probability at least 1−δ1-δ, for each coordinate j∈[d]j∈[d], |1T∑t=1T∑i=1K([i∈At]−[[i∈At]])ci(j)|≤Mc¯2log(2d/δ)T. | 1T _t=1^T _i=1^K(1[i∈ A_t]-E[1[i∈ A_t]])c_i^(j) |≤M c 2 (2d/δ)T. Therefore, for an absolute constant L>0L>0, dist(1T∑t=1T∑i=1K[i∈At]ci,1T∑t=1T[ℓt])≤Mc¯Ldlog(2d)T.E\;dist\! ( 1T _t=1^T _i=1^K1[i∈ A_t]\,c_i,\; 1T _t=1^TE[ _t] )≤M cL d (2d)T. Proof. Step 1: High-probability event. Define Yt:=∑i=1K([i∈At]−[[i∈At]∣ℋt−1])ciY_t:= _i=1^K(1[i∈ A_t]-E[1[i∈ A_t] _t-1])c_i. For each coordinate j∈[d]j∈[d], [Yt(j)∣ℋt−1]=0E[Y_t^(j) _t-1]=0, so (Yt(j),ℋt)(Y_t^(j),H_t) is a martingale difference sequence. Moreover, for each coordinate j∈[d]j∈[d], [Yt(j)∣ℋt−1]=0E[Y_t^(j) _t-1]=0 and Yt(j)∈[−Mc¯,Mc¯]Y_t^(j)∈[-M c,M c] as ci(j)∈[0,c¯]c_i^(j)∈[0, c] and |At|≤M|A_t|≤ M. Let Y¯:=1T∑t=1TYt∈ℝd Y:= 1T _t=1^TY_t ^d. By Azuma–Hoeffding, Pr(|Y¯(j)|≥ϵ)≤2exp(−Tϵ22M2c¯2). ( | Y^(j) |≥ε )≤ 2 (- Tε^22M^2 c^2 ). Applying a union bound over j∈[d]j∈[d] and setting ϵ=Mc¯2log(2d/δ)Tε=M c 2 (2d/δ)T, with probability at least 1−δ1-δ: |Y¯(j)|≤Mc¯2log(2d/δ)Tfor all j∈[d]. | Y^(j) |≤M c 2 (2d/δ)T all j∈[d]. Call this event ℰ(δ)E(δ). Step 2: ℓ2 _2 bound. On event ℰ(δ)E(δ): ‖Y¯‖2=∑j=1d(Y¯(j))2≤d⋅2M2c¯2log(2d/δ)T=2dM2c¯2log(2d/δ)T.\| Y\|_2= _j=1^d( Y^(j))^2≤ d· 2M^2 c^2 (2d/δ)T= 2dM^2 c^2 (2d/δ)T. Step 3: Integration. ‖Y¯‖2=∫0∞ℙ(‖Y¯‖2>u)u.E\| Y\|_2= _0^∞P\! (\| Y\|_2>u )du. Choose δ=δ(u)δ=δ(u) to make the threshold equal u: 2dM2c¯2log(2d/δ)T=u⟹δ(u)=2dexp(−Tu22dM2c¯2). 2dM^2 c^2 (2d/δ)T=u δ(u)=2d \! (- Tu^22dM^2 c^2 ). On ℰ(δ)E(δ), ‖Y¯‖2≤u\| Y\|_2≤ u, so ℙ(‖Y¯‖2>u)≤δ(u)P(\| Y\|_2>u)≤δ(u), giving: ‖Y¯‖2≤∫0∞min(1, 2dexp(−Tu22dM2c¯2))u.E\| Y\|_2≤ _0^∞ \! (1,\ 2d \! (- Tu^22dM^2 c^2 ) )du. Split at u0=2dM2c¯2log(2d)Tu_0= 2dM^2 c^2 (2d)T (where 2dexp(−Tu02/2dM2c¯2)=12d (-Tu_0^2/2dM^2 c^2 )=1): ‖Y¯‖2≤∫0u01du⏟=u0+∫u0∞2dexp(−Tu22dM2c¯2)u.E\| Y\|_2\;≤\; _0^u_01\,du_=\;u_0\;+\; _u_0^∞2d \! (- Tu^22dM^2 c^2 )du. Using the Gaussian tail bound ∫ν∞e−t2/a2dt≤a22νe−ν2/a2 _ν^∞e^-t^2/a^2dt≤ a^22νe^-ν^2/a^2 with a2=2dM2c¯2/Ta^2=2dM^2 c^2/T: ∫u0∞2de−Tu2/(2dM2c¯2)du≤2d2M2c¯2Tu0⋅e−Tu02/(2dM2c¯2)=2d2M2c¯2Tu0⋅12d=dM2c¯22Tlog(2d). _u_0^∞2d\,e^-Tu^2/(2dM^2 c^2)\,du≤ 2d^2M^2 c^2Tu_0· e^-Tu_0^2/(2dM^2 c^2)= 2d^2M^2 c^2Tu_0· 12d= dM^2 c^22T (2d). Combining: ‖Y¯‖2≤2dM2c¯2log(2d)T+dM2c¯22Tlog(2d)≤Mc¯Ldlog(2d)TE\| Y\|_2\;≤\; 2dM^2 c^2 (2d)T+ dM^2 c^22T (2d)\;≤\;M cL d (2d)T for an absolute constant L>0L>0. ∎ Proof of Theorem 2. Taking expectations on (10) and applying Lemma 5 & 6 gives the result. ∎ Appendix D Contextual Algorithm and Proof of Corollary 2 1. Input: rescaled set S, OCO algorithm A, context set X, step-size constant a=2KM(1γ+M−1)a=2 KM( 1γ+M-1) 2. Set ⊂ℝdB ^d to be the unit Euclidean ball, as decision set for A 3. For each x∈x : set qi(x):=1/Kq^(x)_i:=1/K for i∈[K]i∈[K], g(x):=g^(x):=0, and visit count n(x):=0n^(x):=0 4. For t=1,…,Tt=1,…,T: (a) Observe the context x←xtx← x_t and increment n(x)←n(x)+1n^(x)← n^(x)+1 (b) Set ft−1(w)=w⊤ut−1−hS(w)f_t-1(w)=w u_t-1-h_S(w), where ut−1=∑i=1Kqt−1,i(x)ciu_t-1= _i=1^Kq_t-1,i^(x)\;c_i (c) Query A: wt←(f1,…,ft−1)w_t (f_1,…,f_t-1) (d) Set the per-context anytime proximal parameter η←an(x)η← a n^(x) (e) Update only the current context’s iterate, using its own stored gradient g(x)g^(x): q(x)←argmaxq∈ΔK:q≥γq⊤g(x)−η2‖q−q(x)‖2s.t. wt⊤∑i=1Kqici−hS(wt)≤0 splitq^(x)← _q∈ _K:\;q≥γ& q g^(x)- η2 \|q-q^(x) \|^2\\ s.t. &w_t _i=1^Kq_i\;c_i-h_S(w_t)≤ 0 split (12) (f) Draw at,1,…,at,Ma_t,1,…,a_t,M independently from q(x)q^(x); set At←at,j:j∈[M]A_t←\a_t,j:j∈[M]\ (g) Observe rt(At)r_t(A_t) (h) Refresh the current context’s gradient: for each i∈[K]i∈[K], gi(x)←rt(At)qi(x)∑j=1Mat,j=ig^(x)_i← r_t(A_t)q_i^(x) _j=1^MI\! \a_t,j=i \ Algorithm 2 Contextual OMD with Approachability Constraints Proof of Corollary 2. Write G2:=KM(1γ+M−1)G^2:=KM ( 1γ+M-1 ), so that a=2Ga=2G. Fix a context x∈x . Let T(x)T^(x) be the number of rounds with xt=x_t=x, and index these visits by s=1,…,T(x)s=1,…,T^(x). The iterates qs(x)\q_s^(x)\ evolve exactly as Algorithm 1 restricted to this subsequence, with proximal parameters ηs(x)=as _s^(x)=a s. Applying the one-step inequality established in Step 1 of the proof of Theorem 1 (with the filtration argument and conditional expectation taken with respect to the history of the context-c process), we obtain after summing over s=1,…,T(x)s=1,…,T^(x), for any per-context comparator q⋆(x)∈ℱ∘(x)q^(x)_ _ ^(x) [∑s=1T(x)(Φrs(q⋆(x))−Φrs(qs(x)))]≤∑s=1T(x)ηs(x)2(‖q⋆(x)−qs(x)‖2−‖q⋆(x)−qs+1(x)‖2)+∑s=1T(x)2G2ηs(x),E\! [ _s=1^T^(x) ( ^r_s(q^(x)_ )- ^r_s(q_s^(x)) ) ]≤ _s=1^T^(x) _s^(x)2 (\|q^(x)_ -q_s^(x)\|^2-\|q^(x)_ -q_s+1^(x)\|^2 )+ _s=1^T^(x) 2G^2 _s^(x), where the two inner-product terms disappear exactly as in the proof of Theorem 1. For the first sum, Abel summation with the simplex diameter ‖q⋆(x)−qs(x)‖2≤2\|q^(x)_ -q^(x)_s\|^2≤ 2 gives a telescoping bound, ∑s=1T(x)ηs(x)2(‖q⋆(x)−qs(x)‖2−‖q⋆(x)−qs+1(x)‖2)≤η1(x)+∑s=2T(x)(ηs(x)−ηs−1(x))=ηT(x)(x)=aT(x). _s=1^T^(x) η^(x)_s2 ( \|q^(x)_ -q^(x)_s \|^2- \|q^(x)_ -q^(x)_s+1 \|^2 )\;≤\;η^(x)_1+ _s=2^T^(x) (η^(x)_s-η^(x)_s-1 )\;=\;η^(x)_T^(x)\;=\;a T^(x). For the second sum, ∑s=1T(x)1ηs(x)=1a∑s=1T(x)s−1/2≤2aT(x). _s=1^T^(x) 1 _s^(x)= 1a _s=1^T^(x)s^-1/2≤ 2a T^(x). Hence the expected regret for context c satisfies [∑s=1T(x)(Φrs(q⋆(x))−Φrs(qs(x)))]≤(a+4G2a)T(x)=4GT(x),E\! [ _s=1^T^(x) ( ^r_s(q^(x)_ )- ^r_s(q_s^(x)) ) ]≤ (a+ 4G^2a ) T^(x)=4G T^(x), where the last equality uses a=2Ga=2G. Summing over all contexts and applying Cauchy–Schwarz (i.e., ∑x∈T(x)≤||T, _x T^(x)≤ |X|\,T,), yields T[R1ctx(T)] T\,E\! [R_1^ctx(T) ] ≤4G∑x∈T(x) ≤ 4G _x T^(x) ≤4G||T ≤ 4G |X|\,T =4||TKM(1γ+M−1), =4 |X|\,TKM ( 1γ+M-1 ), which proves the result. ∎