Source-linked AI summary
Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift
Fredy Pokou
TL;DR
Online allocation must use potentially unreliable predictions while preserving efficiency and exposure fairness. The paper combines learned advice, a conservative fallback, and virtual-queue correction, proving error-sensitive guarantees and finding stable efficiency with sharply reduced exposure disparity under adversarial advice.
Problem
Online allocation needs robust decisions when learned advice can be misspecified, distribution-shifted, or biased, while exposure constraints must also be controlled.
Method
The proposed rule interpolates advice with conservative fallback scores and penalizes cumulative exposure imbalance using virtual queues.
Results
FAIR-LA sharply reduces exposure disparity under adversarial advice without collapsing in competitive ratio, while ROBUST-LA protects efficiency under unreliable advice.
Takeaways & Limitations
Finite-horizon guarantees and MovieLens-derived experiments support a robust efficiency–fairness compromise under unreliable advice.
Takeaways & Limitations
The theory assumes bounded finite slates and corrective availability for replacing over-exposed groups with alternatives of limited robust-score loss.
Abstract
from arXiv · showhide
Learning-augmented algorithms improve online decisions using predictions, but unreliable advice may harm efficiency and fairness. We study an online allocation problem with finite candidate sets, irreversible decisions, and exposure constraints. We propose a robust and fair rule combining advice with a conservative fallback and fairness correction. Under bounded-error assumptions, we prove consistency and robustness with loss proportional to prediction error. Experiments show stability under adversarial advice and significant reductions in exposure disparity.
1 Introduction
The paper asks whether learned advice can improve online allocation without sacrificing robustness or exposure fairness. It proposes a robust/fair rule and derives guarantees and experiments covering accurate, inaccurate, adversarial, and shifted advice.
- Motivation: Online allocation needs to balance worst-case robustness with the average-case benefits of data-driven predictions.Purely data-driven rules may fail under misspecification, distribution shift, or biased predictions.
- Proposed approach: The paper combines predictive advice with a conservative fallback and virtual-queue fairness correction.This is the proposed robust and fair learning-augmented rule.
- Theory: The robust rule is consistent with accurate advice while retaining conservative protection when advice is inaccurate.The paper also gives an advice-relative robustness certificate and a finite-time exposure bound.
- Evaluation: Experiments use reproducible MovieLens-derived allocation instances with benign noise, adversarial advice, and distribution shift.The evaluation is designed to test both reliability and fairness across advice conditions.
2 Model
The model is a finite-horizon online allocation process with irrevocable actions, rewards, item groups, and exposure targets. Each arriving request provides a finite feasible slate together with learned and conservative scores.
- Online process: At each of T periods, a request reveals a finite feasible slate, and the decision-maker chooses one action irrevocably.The chosen action produces a reward in [0, 1].
- Exposure structure: Items belong to a finite set of groups, allowing cumulative exposure to be tracked against group targets.Group membership is denoted by g(i), while exposure targets are represented by ρ_g.
- Signals: Before each decision, the policy observes a learned advice vector and a conservative fallback vector on the feasible slate.The two score sources support both prediction use and conservative protection.
- Benchmark: The benchmark is slate-wise and intentionally strong, with capacitated variants interpreted through the remaining feasible actions.This makes the comparison demanding while accommodating irreversible feasibility constraints.
- Evaluation quantities: The model defines average advice and fallback errors, an exposure gap, and an advice-only policy for analysis.These quantities support separate efficiency, error, and fairness comparisons.
3 Algorithm
The algorithm interpolates learned advice with conservative fallback scores and subtracts a virtual-queue penalty for group exposure imbalance. It then chooses the highest penalized score and updates the queues after each irrevocable action.
- Robust scoring: RLA selects actions using a robust score that combines predictive advice with a conservative fallback.The interpolation weight α controls the balance between the two score sources.
- Fairness correction: Virtual imbalances track cumulative deviations from target exposure across groups.These queues provide the state used for fairness correction.
- Procedure: At each period, the policy observes the slate and scores, computes sα_t(i) = (1 −α)r̂_t(i) + αb_t(i), and chooses the action maximizing penalized score.The penalty is λQ_t(g(i)) for the selected item's group.
- Procedure: The queue update adds one for the selected group and subtracts its target exposure after every decision.This update carries exposure imbalance forward to later choices.
4 Theory
Under bounded finite slates and a non-degenerate benchmark, the theory gives consistency and robustness guarantees tied to advice and fallback error. A corrective-availability condition yields finite-time exposure control, while interpolation also limits advice manipulation.
- Assumptions: The results are deterministic conditional on the realized slates, rewards, advice, and fallback scores.The guarantees do not require additional randomness once this sequence is fixed.
- Assumptions: The analysis assumes finite slates with scores and rewards in [0, 1], plus OPT_T ≥ωT for a non-degenerate benchmark.These are the bounded-slate and benchmark conditions underlying the main guarantee.
- Efficiency guarantees: Theorem 1 establishes a finite-horizon consistency-robustness bound for every α ∈[0, 1].The bound is obtained using perturbation stability and leads to a normalized guarantee under the benchmark assumption.
- Fallback protection: The robust policy remains protected when the conservative score has bounded error, irrespective of advice error.This is the fallback-protection consequence of the theory.
- Advice-relative guarantee: The advice-relative certificate is proved by combining the advice-only upper bound with the robust policy's lower bound.This proof connects the main consistency-robustness result to the certificate.
- Exposure control: Under corrective availability, excessive pairwise group imbalance cannot keep increasing, yielding a finite-time exposure bound.The replacement condition limits robust-score loss when correcting over-exposed groups.
- Incentive dampening: Advice manipulation of size m changes the decision score by at most (1−α)m, making manipulation with higher cost unprofitable.The result applies to both RLA and FLA.
5 Computational study
The computational study evaluates the proposed policies on MovieLens-derived online allocation instances under benign noise, adversarial advice, and distribution shift. ROBUST-LA preserves efficiency under unreliable advice, while FAIR-LA combines high efficiency with substantially lower exposure disparity.
- Experimental setup: MovieLens-derived instances treat arriving users as online requests and movies as feasible slate items, with irrevocable selections and rescaled ratings as rewards.Advice comes from matrix factorization, while conservative scores are popularity-calibrated; groups define exposure categories and targets use the empirical candidate-pool distribution.
- Experimental setup: The experiments compare RANDOM, POPULARITY, ADVICE, ROBUST-LA, and FAIR-LA using competitive ratio and exposure fairness gap.The robustness analysis additionally reports empirical advice error εT and competitive-ratio gain relative to ADVICE.
- Robustness and efficiency: Across benign noise, distribution shift, and adversarial advice, ROBUST-LA and FAIR-LA remain close to or above ADVICE without collapse as advice error increases.Figure 1 places the observed competitive-ratio gains above the −εT envelope, consistent with the advice-relative guarantee.
- Robustness and efficiency: The learning-augmented policies retain a clear efficiency advantage over RANDOM and POPULARITY, whose competitive ratios remain near 0.81 under distribution shift.ROBUST-LA and FAIR-LA remain stable as σ varies in benign and adversarial regimes, while learning-augmented policies retain high competitive ratios under shift.
- Fairness: FAIR-LA lies on the favorable efficiency–fairness frontier by sacrificing little competitive ratio while achieving substantially lower exposure disparity.POPULARITY can occasionally have a small fairness gap, but at much lower competitive ratio.
- Fairness: FAIR-LA substantially reduces exposure disparity under adversarial advice while preserving nearly the same competitive ratio as ADVICE.It also achieves the lowest or near-lowest exposure gap across most noise levels in benign and shifted regimes.
6 Conclusion
The paper studies online allocation with learned advice, conservative fallback scores, and exposure-fairness targets. Its simple interpolation and virtual-queue correction yield finite-horizon guarantees, while experiments support efficiency protection and the strongest efficiency–fairness compromise for FAIR-LA.
- Conclusion: The proposed rule interpolates between advice and fallback scores, then penalizes cumulative exposure imbalance.A virtual-queue argument provides finite-time exposure control.
- Conclusion: The central bound makes performance degrade with a weighted combination of advice error and fallback error.The corollaries recover consistency, fallback protection, and CRT(RLA) ≥CRT(ADV) −O(εT).
- Conclusion: On MovieLens-derived instances, ROBUST-LA protects efficiency under unreliable advice while FAIR-LA provides the strongest efficiency–fairness compromise.FAIR-LA sharply reduces exposure disparity under adversarial advice without collapsing in competitive ratio.
Data Availability
The numerical experiments are based on synthetic benchmark environments generated algorithmically by the authors.
- Data Availability: All numerical experiments use synthetic benchmark environments generated algorithmically by the authors.
Code Availability
The code used to generate benchmarks, compute optimal policies, train baselines, and reproduce the reported outputs is available from the corresponding author upon reasonable request.
- Code Availability: Code for benchmark generation, dynamic-programming optimal policies, baseline training, and reproducing tables and figures is available upon reasonable request.