Problem formalization:
- Environment: M services i∈{1..M}, T decision rounds. Each round t we allocate a vector of discrete resources a_t = (a_{t,1},...,a_{t,M}) from a feasible budget set A (e.g., ∑i c_i a{t,i} ≤ C, per-host caps).
- Reward: stochastic QoS reward r_t = ∑i R_i(a{t,i}, s_{t,i}) where s_{t,i} are unknown service states (load, SLO attainment); we observe rewards (possibly delayed/noisy) after allocation. Objective: maximize cumulative expected reward E[∑_{t=1}^T r_t] (or minimize regret vs best fixed allocation/policy).
- Unknowns: response curves R_i(·) (monotone, possibly concave), cross-service interactions (contention).
Why this is a combinatorial bandit:
- Each action is a combinatorial object (vector allocation under constraints) drawn from an exponential-size set A. Reward decomposes (possibly approximately) over arms (services) but choice couples via budget constraints. Observations may be semi-bandit (per-service feedback) or bandit (only aggregate). This matches combinatorial multi-armed bandits (CMAB).
Algorithmic solutions:
- Approximate Combinatorial UCB (CMUCB):
- Maintain per-service estimates μ̂_i(a) or parametric models (e.g., diminishing returns curve). Compute optimistic estimates μ̂_i + bonus_i(t) and solve an offline knapsack/ILP to pick allocation maximizing sum of optimistic rewards subject to constraints. Use approximation-aware regret bounds: if offline oracle is α-approx, regret scales O((poly)·T/α). Use structured models (GLM, parametric) to reduce sample complexity.
- Greedy with submodular objectives:
- If ∑i R_i(a{i}) is monotone submodular in discrete resource units, use greedy hill-climbing per round: iteratively allocate marginal unit with largest estimated marginal gain. With (1-1/e) approximation and confidence bonuses, this gives provable approximate regret. Practical variant: Thompson Sampling + greedy sampling to handle uncertainty.
- Contextual/parametric bandits:
- Use contextual CMAB: include features (current load, queues). Fit online Bayesian/linear models and use LinUCB/Thompson Sampling over allocations with efficient combinatorial optimization via knapsack solvers.
- Handling interactions:
- If strong cross-coupling, treat joint arms for small groups or use low-rank factorization of interaction matrix and learn latent factors.
Practical monitoring and risk controls:
- Safety constraints: enforce hard SLO-preserving actions (never drop below reserve allocations), and clipping of exploratory allocations.
- Conservative bootstrapping: begin with off-line A/B tests or simulation to initialize priors; use decaying exploration rates.
- Canary & rollback: stage policy in canary cluster with traffic shadowing; automatic rollback on SLO degradation beyond thresholds.
- Observability: per-service QoS, latencies, error rates, resource usage, and reward attribution with high-cardinality logs; compute regret/expected reward delta vs baseline in real-time.
- Alarm & intervention: require human-in-loop for high-impact allocation changes, throttle exploratory updates when variance or delayed feedback increases.
- Explainability: surface marginal gains used for each allocation decision to operators.
Trade-offs:
- Exact CMAB algorithms give theoretical guarantees but need efficient oracles; greedy/submodular methods scale well and are robust if submodularity approx holds. Contextual models reduce samples but require reliable features.
This design balances provable algorithms with practical safety: start with parametric/contextual CMUCB + greedy allocation, strong monitoring and safety gates, then iterate as more data reduces uncertainty.
