Paper deep dive
Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift
Fredy Pokou
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/28/2026, 4:24:16 AM
Summary
This paper introduces a robust and fair learning-augmented algorithm for online allocation problems. The proposed method combines learned predictive advice with a conservative fallback score and a virtual-queue mechanism to correct exposure disparities among groups. Theoretical analysis proves consistency when advice is accurate and robustness (bounded loss) when advice is unreliable, providing an advice-relative robustness certificate. Experiments on MovieLens data demonstrate that the Fair Robust Learning-Augmented (FLA) policy significantly reduces exposure disparity compared to advice-only policies while maintaining high competitive ratios under benign noise, adversarial advice, and distribution shift.
Entities (8)
Relation Signals (6)
Frédy Pokou → authored → Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift
confidence 98% · Preprint, compiled August 28, 2026 Frédy. Pokou
RLA → combines → Learned Advice
confidence 95% · The robust policy RLA selects a RLA t ∈ arg max i∈A t s α t (i) where s α t (i) = (1− α)ˆr t (i) + αb t (i).
FLA → uses → Virtual Queue
confidence 95% · For λ≥ 0, the fair robust policy FLA selects a FLA t ∈ arg max i∈A t {s α t (i)− λQ t (g(i))}.
RLA → provides → Consistency and Robustness
confidence 92% · Under bounded-error assumptions, we prove consistency and robustness with loss proportional to prediction error.
FLA → reduces → Exposure Fairness Gap
confidence 90% · FAIR-LA sharply reduces exposure imbalance, especially under adversarial advice
MovieLens 1M → usedfor → FLA
confidence 90% · We evaluate the proposed policies on online allocation instances derived from the MovieLens 1M data set.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2608.26889v1
- Canonical: https://arxiv.org/abs/2608.26889v1
Trouble viewing inline? Open PDF directly →
Full Text
15,969 characters extracted from source content.
Expand or collapse full text
Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift Preprint, compiled August 28, 2026 Frédy. Pokou ID 1 ∗ 1 Inria, University of Lille, CNRS, Centrale Lille Villeneuve-d’Ascq, France Abstract 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. Keywords Learning-augmented algorithms·Online allocation·Competitive analysis·Exposure fairness·Distribution shift· Robust decision-making. 1 Introduction Online allocation problems arise in recommendation, advertis- ing, labor-market platforms, and matching systems. Classical online algorithms provide worst-case guarantees, but may be conservative; purely data-driven rules can perform well on av- erage, but may fail under misspecification, distribution shift, or biased predictions. Learning-augmented algorithms address this tension by using predictions while retaining robustness guar- antees [Lykouris and Vassilvitskii, 2021, Purohit et al., 2018, Mitzenmacher and Vassilvitskii]. Classical online matching and advertising allocation provide the algorithmic background [Karp et al., 1990, Mehta et al., 2007], while exposure-based fairness constraints are central in ranking and recommendation [Singh and Joachims, 2018]. This paper studies whether learned advice can be used in online allocation while preserving robustness and controlling exposure imbalance. We propose a robust and fair learning-augmented rule that combines predictive advice with a conservative fallback and a virtual-queue fairness correction. Contributions. First, we formulate a finite-horizon online al- location model with learned advice, conservative scores, and exposure targets. Second, we introduce a robust/fair learning- augmented policy. Third, we prove a central finite-sample guar- antee: the robust rule is simultaneously consistent when advice is accurate and protected by a conservative fallback when ad- vice is inaccurate. We also derive an advice-relative robustness certificate of the form CR T (RLA)≥ CR T (ADV)− O(ε T ), and a finite-time exposure bound for the fair rule. Fourth, we provide reproducible experiments on MovieLens-derived online allocation instances under benign noise, adversarial advice, and distribution shift. 2 Model LetT ∈Nbe the horizon. At each timet ∈[T], a request arrives and the decision-maker observes a finite feasible slate A t ⊆ I. The actiona t ∈ A t is chosen irrevocably and yields rewardr t (a t )∈[0,1]. Each itemi ∈ Ibelongs to a group g(i)∈G, whereGis finite. Before choosing, the decision-maker observes two score vectors onA t : a learned advice vectorˆr t and a conservative fallback vector b t . For a policy π, let a π t be its action and W T (π) = T X t=1 r t (a π t ).(1) The offline benchmark is OPT T = T X t=1 max i∈A t r t (i),CR T (π) = W T (π) OPT T ,(2) wheneverOPT T >0. This benchmark is slate-wise and inten- tionally strong. In capacitated variants,A t can be interpreted as the remaining feasible actions after past decisions. The average advice and fallback errors are ε T = 1 T T X t=1 ∥ˆr t − r t ∥ ∞,A t , κ T = 1 T T X t=1 ∥b t − r t ∥ ∞,A t .(3) For a target exposure vector ρ∈ ∆(G), group exposure is E π T (g) = 1 T T X t=1 1g(a π t ) = g,(4) and the exposure gap is Gap ρ T (π) = max g∈G |E π T (g)− ρ g |.(5) The advice-only policy is a ADV t ∈ arg max i∈A t ˆr t (i).(6) 3 Algorithm For α∈ [0, 1], define the robust learning-augmented score s α t (i) = (1− α)ˆr t (i) + αb t (i).(7) arXiv:2608.26889v1 [cs.AI] 27 Aug 2026 2 The robust policy RLA selects a RLA t ∈ arg max i∈A t s α t (i).(8) To control exposure, define virtual imbalances Q t (g) = t−1 X s=1 1g(a s ) = g− ρ g ,Q 1 (g) = 0.(9) For λ≥ 0, the fair robust policy FLA selects a FLA t ∈ arg max i∈A t s α t (i)− λQ t (g(i)).(10) Algorithm 1 Fair Robust Learning-Augmented Allocation Require: α∈ [0, 1], λ≥ 0, target exposure ρ∈ ∆(G) 1: Initialize Q 1 (g) = 0 for all g∈G. 2: for t = 1,..., T do 3:ObserveA t , ˆr t , and b t . 4:Compute s α t (i) = (1− α)ˆr t (i) + αb t (i). 5:Choose a t ∈ arg max i∈A t s α t (i)− λQ t (g(i)). 6:Update Q t+1 (g) = Q t (g) + 1g(a t ) = g− ρ g . 7: end for 4 Theory All results are deterministic conditional on the realized sequence (A t , r t , ˆr t , b t ) T t=1 . Assumption 1 (Bounded finite slates). For alltandi ∈ A t , r t (i), ˆr t (i), b t (i)∈ [0, 1], and 1≤|A t | <∞. Assumption 2 (Non-degenerate benchmark). There existsω >0 such that OPT T ≥ ωT . Lemma 1 (Perturbation stability). Lets t be any score vector on A t , and let a s t ∈ arg max i∈A t s t (i). Then max i∈A t r t (i)− r t (a s t )≤ 2∥s t − r t ∥ ∞,A t . Proof. Let i ⋆ t ∈ arg max i∈A t r t (i). Since s t (a s t )≥ s t (i ⋆ t ), r t (i ⋆ t )− r t (a s t )≤|r t (i ⋆ t )− s t (i ⋆ t )| +|s t (a s t )− r t (a s t )|. The result follows by taking the maximum norm overA t . Theorem 1 (Central consistency-robustness bound). Under As- sumption 1, for every α∈ [0, 1], OPT T − W T (RLA)≤ 2T (1− α)ε T + ακ T . Consequently, under Assumption 2, CR T (RLA)≥ 1− 2 ω (1− α)ε T + ακ T . Proof. For each t, ∥s α t − r t ∥ ∞,A t ≤ (1− α)∥ˆr t − r t ∥ ∞,A t + α∥b t − r t ∥ ∞,A t . Apply Lemma 1 withs t =s α t , sum overt, and divide byOPT T ≥ ωT . Corollary 2 (Consistency). If α = 0, then CR T (ADV)≥ 1− 2ε T ω . In particular, perfect advice (ε T = 0) is offline-optimal. Corollary 3 (Robust fallback protection). If α = 1, then CR T (RLA)≥ 1− 2κ T ω . Thus the policy remains protected whenever the conservative score has bounded error, irrespective of the advice error. Corollary 4 (Advice-relative certificate). Under Assumptions 1– 2, CR T (RLA)≥ CR T (ADV)− 2α ω (κ T + ε T ). Hence, if κ T = O(ε T ), then CR T (RLA)≥ CR T (ADV)− O(ε T ). Proof. By Corollary 2,CR T (ADV)≤1 and its loss from one is at most 2ε T /ω. Theorem 1 gives the corresponding lower bound for RLA. Combining the two inequalities yields the claim. Assumption 3 (Corrective availability). There existδ >0 and ∆∈[0,1] such that, wheneverQ t (g)− Q t (h)> δT, any avail- able item from the over-exposed groupgcan be replaced by an available item from grouphwhose robust score is lower by at most ∆. Theorem 5 (Finite-time exposure control). Under Assump- tions 1 and 3, if λ > ∆ δT , then max g,h∈G Q T +1 (g)− Q T +1 (h)≤ δT + 2. Consequently, Gap ρ T (FLA)≤ δ + 2 T . Proof.SupposeQ t (g)− Q t (h)> δT. By Assumption 3, an available group-gitem can be replaced by a group-hitem with robust-score loss at most ∆. The penalized-score advantage of the group-g item is then at most ∆− λ(Q t (g)− Q t (h)) < 0. Thus the policy cannot increase an already excessive pairwise imbalance. Since one decision changes any pairwise imbalance by at most two, the queue bound follows. Finally,Q T +1 (g) = T (E T (g)− ρ g ), which gives the exposure-gap bound. Proposition 6 (Incentive dampening). If an item can change its advice score by at mostm ≥0, then its one-period score gain underRLAorFLAis at most (1−α)m. Hence any manipulation of size m with cost larger than (1− α)m is unprofitable. Proof. The advice enters the decision score only through the coefficient 1− α. A perturbation of magnitudemcan therefore change the score by at most (1− α)m. 3 5 Computational study We evaluate the proposed policies on online allocation instances derived from the MovieLens 1M data set. The raw data contain user-movie ratings. We interpret each arriving user as an online request and the available movies as the feasible slate. Ratings are rescaled to [0,1] and used as realized rewards. At each period, the policy selects one movie from the slate irrevocably. Instance construction. A matrix-factorization model is trained on a fixed training split and used to generate the advice vectorˆr t . The conservative scoreb t is a popularity-calibrated score, adjusted to avoid over-reliance on the learned predictor. Candidate slates contain both high-score items and lower-quality decoy items, so that random and popularity policies are nontriv- ial but not artificially favored. Movie groups define the expo- sure categories, and the target vectorρis set to the empirical group distribution in the candidate pool. All results are averaged over independent arrival sequences generated with fixed random seeds. Stress regimes. We consider three regimes. In the benign regime, advice is perturbed by mean-zero noise of levelσ. In the adversarial-advice regime, advice is systematically biased across exposure groups, mimicking strategic or discriminatory score distortion. In the distribution-shift regime, test arrivals over-sample a subpopulation whose preferences differ from the training distribution. These regimes are designed to test the consistency–robustness trade-off predicted by Theorem 1 and Corollary 4. Policies and metrics. We compare RANDOM, POPULAR- ITY, ADVICE, ROBUST-LA, and FAIR-LA. Performance is measured by the empirical competitive ratioCR T relative to the slate-wise offline benchmark and by the exposure fairness gap Gap ρ T . For the robustness certificate, we also report the empiri- cal advice errorε T and the gain in competitive ratio relative to ADVICE. Figure 1: Robustness certificate across scenarios. The vertical axis reports the competitive-ratio gain over ADVICE and the horizontal axis reports the empirical advice errorε T . The dashed line is the−ε T envelope. The points remain above this envelope, in line with the error-dependent guarantee in Corollary 4. Figure 1 provides the empirical counterpart of the advice-relative robustness certificate. Across benign noise, distribution shift, and adversarial advice, ROBUST-LA and FAIR-LA remain close to or above the advice-only rule, with no collapse as advice error increases. This supports the interpretation that conservative interpolation prevents catastrophic degradation when predictions are unreliable. Figure 2: Competitive ratio under prediction noise. ROBUST- LA and FAIR-LA preserve high competitive ratios across the three stress regimes, while RANDOM and POPULARITY are consistently separated from the learning-augmented policies. Figure 2 shows that the learning-augmented policies retain a clear efficiency advantage over RANDOM and POPULARITY. In the adversarial and benign regimes, the proposed rules remain stable asσvaries. Under distribution shift, competitive ratios remain high for all learning-augmented policies, while non- personalized baselines stay near 0.81. Figure 3: Exposure fairness gap under prediction noise. FAIR- LA sharply reduces exposure imbalance, especially under ad- versarial advice, where the advice-only policy induces large disparities. Figure 3 confirms the role of the virtual exposure correction. Under adversarial advice, ADVICE produces severe exposure imbalance, whereas FAIR-LA reduces the gap substantially. In benign and shifted regimes, FAIR-LA also delivers the lowest or near-lowest exposure gap over most noise levels. POPULARITY can occasionally have a small fairness gap, but this is obtained with much lower competitive ratio; hence it does not provide the same efficiency-fairness trade-off. Figure 4: Efficiency–fairness frontiers. Each point reports the average competitive ratio and exposure fairness gap of one pol- icy. FAIR-LA lies on the favorable frontier by combining high efficiency with low exposure disparity. 4 Figure 4 summarizes the trade-off. FAIR-LA is the most sta- ble policy on the efficiency–fairness frontier: it sacrifices little competitive ratio relative to ROBUST-LA or ADVICE while achieving substantially lower exposure disparity. This is the main empirical message of the study. BenignDist. ShiftAdversarial Noise (σ) PolicyCR↑ FG↓CR↑ FG↓CR↑ FG↓ 0.00 ADVICE0.7430.0220.9050.0220.7140.594 POPULARITY0.6740.0200.8080.0220.677 0.038 RANDOM0.6760.0190.8110.0160.6870.196 ROBUST-LA0.7460.0220.9050.0130.7210.494 FAIR-LA0.755 0.012 0.915 0.010 0.7220.339 0.10 ADVICE0.7640.0300.8980.014 0.7260.620 POPULARITY0.6800.0240.8100.0220.681 0.031 RANDOM0.6860.0270.8170.0220.6900.217 ROBUST-LA0.7690.0240.9030.0170.7230.498 FAIR-LA0.771 0.008 0.904 0.0130.7250.288 0.50 ADVICE0.7130.0170.8600.0200.7290.149 POPULARITY0.6730.0250.8160.0200.6900.029 RANDOM0.6820.024 0.8190.0130.6930.020 ROBUST-LA0.7120.0180.8550.021 0.7290.091 FAIR-LA0.712 0.0060.858 0.0060.728 0.015 Table 1: Performance Comparison across Scenarios. We report the mean Competitive Ratio (CR↑) and Fairness Gap (FG ↓). Robust-LA and Fair-LA consistently bridge the gap between pure Advice and baseline policies. Table 1 reports representative noise levels. The table highlights two points. First, RANDOM and POPULARITY are not com- petitive in efficiency: they are consistently below the learning- augmented policies in CR. Second, FAIR-LA achieves the most reliable fairness improvement. In adversarial settings, ADVICE can achieve high CR but at the cost of extreme exposure gaps; FAIR-LA substantially reduces this disparity while preserving nearly the same CR. 6 Conclusion We studied online allocation with learned advice, conservative fallback scores, and exposure-fairness targets. The proposed rule is deliberately simple: interpolate between advice and fall- back scores, then penalize cumulative exposure imbalance. This simplicity yields finite-horizon guarantees. The central bound shows that performance degrades with a weighted combination of advice error and fallback error; the corollaries recover con- sistency, fallback protection, and the advice-relative certificate CR T (RLA)≥ CR T (ADV)− O(ε T ). A virtual-queue argument gives finite-time exposure control. The computational study supports these conclusions on MovieLens-derived online allocation instances. ROBUST-LA protects efficiency under unreliable advice, while FAIR-LA pro- vides the strongest efficiency–fairness compromise. In particular, FAIR-LA sharply reduces exposure disparity under adversarial advice without collapsing in competitive ratio. Future work may extend the analysis to hard matching capacities and to endoge- nous, strategically generated advice. Data Availability All numerical experiments in this study are based on synthetic benchmark environments generated algorithmically by the au- thors. Code Availability The Python code used to generate the benchmark environments, compute the optimal policies via dynamic programming, train all boundary-based and reinforcement-learning baselines, and reproduce the tables and figures is available from the correspond- ing author upon reasonable request. References Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM), 68(4):1–25, 2021. Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018. Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions seeking a new approach that goes beyond worst-case analysis. Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceed- ings of the twenty-second annual ACM symposium on Theory of computing, pages 352–358, 1990. Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazi- rani. Adwords and generalized online matching. Journal of the ACM (JACM), 54(5):22–es, 2007. Ashudeep Singh and Thorsten Joachims. Fairness of exposure in rankings. In Proceedings of the 24th ACM SIGKDD inter- national conference on knowledge discovery & data mining, pages 2219–2228, 2018.