Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift

1 Introduction

• Online allocation rules face a tension between conservative worst-case guarantees and average-case performance vulnerable to misspecification, distribution shift, or biased predictions.Learning-augmented algorithms address this tension by using predictions while retaining robustness guarantees [Lykouris and Vassilvitskii, 2021, Purohit et al., 2018, Mitzenmacher and Vassilvitskii].Source: §1 · p. 1
• The paper formulates a finite-horizon allocation model with learned advice, conservative scores, and exposure targets, and proposes a robust/fair learning-augmented policy.The policy combines predictive advice with a conservative fallback and a virtual-queue fairness correction.Source: §1 · p. 1
• The robust rule is consistent when advice is accurate and protected by a conservative fallback when advice is inaccurate.The paper also derives an advice-relative robustness certificate and a finite-time exposure bound for the fair rule.Source: §1 · p. 1
• The paper reports reproducible experiments on MovieLens-derived online allocation instances under benign noise, adversarial advice, and distribution shift.The supplied passage describes the experimental settings but does not provide outcome values.Source: §1 · p. 1

• At each of T rounds, a request arrives with a finite feasible slate A_t, from which the decision-maker irrevocably chooses an action.Source: §2 · p. 1
• Each chosen action earns reward r_t(a_t) in [0, 1]; items belong to finite groups, and learned-advice and conservative-fallback score vectors are observed before choosing.Source: §2 · p. 1
• The benchmark is slate-wise and intentionally strong; in capacitated variants, A_t represents the actions still feasible after past decisions.Source: §2 · p. 1
• The model defines average advice and fallback errors and an exposure gap.Source: §2 · p. 1

3 Algorithm

• The algorithm initializes every group’s virtual imbalance to zero and updates the selected group’s imbalance by 1−ρ_g after each allocation.For group g, Q_{t+1}(g) = Q_t(g) + 1{g(a_t)=g} − ρ_g.Source: §3 · p. 2
• At each round, the algorithm observes the candidate set, predicted rewards, and advice before computing scores and allocating.It observes A_t, r̂_t, and b_t.Source: §3 · p. 2
• Each round, RLA chooses a candidate maximizing its blended prediction-advice score minus λ times its group’s virtual imbalance.The score is (1−α)r̂_t(i) + αb_t(i) − λQ_t(g(i)).Source: §3 · p. 2

4 Theory

• The results are deterministic conditional on the realized sequence, and assume bounded rewards, advice scores, and conservative scores on finite candidate slates.The slates are nonempty and finite, and each score lies in [0, 1].Source: §4 · p. 2
• Under Assumption 1, Theorem 1 gives a consistency-robustness bound for every α; the policy remains protected with bounded conservative-score error, irrespective of advice error.Under Assumptions 1–2, the advice-relative certificate states CRT(ADV) ≤1, with loss from one at most 2εT/ω, and combines this with a corresponding lower bound for RLA.Source: §4 · p. 2
• Under corrective availability, the policy bounds pairwise exposure imbalance in finite time and yields an exposure-gap bound.When an imbalance exceeds δT, an available over-exposed-group item can be replaced by one from the other group at robust-score loss at most ∆; one decision changes any pairwise imbalance by at most two.Source: §4 · p. 2
• A change of at most m in an item's advice score can raise its one-period score under RLA or FLA by at most (1 −α)m, so manipulation costing more is unprofitable.Source: §4 · p. 2

5 Computational study

• MovieLens 1M user-movie ratings become irrevocable slate choices with rewards in [0,1], evaluating five policies by competitive ratio and exposure gap.Advice comes from a matrix-factorization model, and the conservative score is popularity-calibrated. Candidate slates include decoys, and tests cover noisy, group-biased advice and shifted arrivals.Source: §5 · p. 3
• Across benign noise, distribution shift, and adversarial advice, ROBUST-LA and FAIR-LA stay near or above ADVICE, with gains above the −εT envelope as advice error rises.The results show no collapse as advice error increases, supporting the error-dependent robustness certificate.Source: Figure 1 · p. 3, §5 · p. 3
• ROBUST-LA and FAIR-LA remain stable as σ varies in benign and adversarial regimes, while learning-augmented policies retain high shifted-regime ratios versus baselines near 0.81.Across regimes, learning-augmented policies retain a clear efficiency advantage over RANDOM and POPULARITY.Source: Figure 2 · p. 3, §5 · p. 3
• FAIR-LA substantially reduces ADVICE’s severe adversarial exposure imbalance and has the lowest or near-lowest gap in benign and shifted regimes, unlike low-efficiency POPULARITY.POPULARITY can occasionally have a small fairness gap, but at much lower competitive ratio.Source: Figure 3 · p. 3, §5 · p. 3
• FAIR-LA preserves nearly the same CR as ROBUST-LA or ADVICE while substantially lowering exposure disparity, yielding a favorable efficiency–fairness trade-off.The study identifies this as its main empirical message.Source: Figure 4 · p. 3, Table 1 · p. 4, §5 · p. 4

6 Conclusion

• Interpolating advice and fallback scores and penalizing cumulative exposure imbalance yields finite-horizon guarantees, including weighted-error degradation, consistency, fallback protection, an advice-relative certificate, and finite-time exposure control.The certificate is CRT(RLA) ≥ CRT(ADV) − O(εT), and finite-time exposure control follows from a virtual-queue argument.Source: §6 · p. 4
• On MovieLens-derived online allocation instances, ROBUST-LA protects efficiency under unreliable advice, while FAIR-LA offers the strongest efficiency–fairness compromise and reduces adversarial exposure disparity without collapsing in competitive ratio.The conclusion identifies extensions to hard matching capacities and endogenous, strategically generated advice as future work.Source: §6 · p. 4

• All numerical experiments use synthetic benchmark environments generated algorithmically by the authors.Source: Data Availability · p. 4