Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Algorithmic Recourse for Long-Term Improvement
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ARLIM, an online learning framework for algorithmic recourse that uses delayed feedback on real-world outcomes to suggest improvement-oriented actions, with contextual linear bandit (LinUCB) and contextual Bayesian optimization (BwO forest UCB) solutions.
Problem
Standard algorithmic recourse only ensures validity with respect to a proxy classifier, not that the action actually improves the true real-world outcome (oracle h*), which is unknown.
Approach
Treats recourse as a long-term online learning problem where delayed observations of whether past suggested actions improved outcomes are used to learn which action improves each instance, via a contextual linear bandit under delayed feedback and a CBO approach with a bagging-with-oversampling forest surrogate.
Key results
- LinUCB and BwOUCB attained higher average improvement than ProtoAR and TAP on all three datasets under noiseless cost evaluation, with LinUCB maintaining comparable cost.
- Under noisy cost evaluation (noise level 0.25), BwOUCB achieved higher average mean expected reward than LinUCB on all datasets in the final round.
- Mean expected reward of LinUCB and BwOUCB increased over rounds, consistent with the theoretical bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LinUCB for long-term recourse instead of ProtoAR or TAP | ARLIM on Credit, Diabetes, and COMPAS · Credit, Diabetes, and COMPAS | average improvement | Helped |
| Use BwOUCB for long-term recourse instead of ProtoAR or TAP | ARLIM on Credit, Diabetes, and COMPAS · Credit, Diabetes, and COMPAS | average improvement | Helped |
| Use LinUCB for long-term recourse instead of ProtoAR or TAP | ARLIM on Credit, Diabetes, and COMPAS · Credit, Diabetes, and COMPAS | average cost | No clear effect |
| Increase the number of rounds using LinUCB | ARLIM · Credit, Diabetes, and COMPAS | average mean expected reward | Helped |
| Increase the number of rounds using BwOUCB | ARLIM · Credit, Diabetes, and COMPAS | average mean expected reward | Helped |
| Add uncertainty to the execution-probability cost evaluation | LinUCB compared with BwOUCB · Credit, Diabetes, and COMPAS | average mean expected reward | Hurt |
| Use BwOUCB instead of LinUCB when execution-probability cost estimates are noisy | ARLIM · Credit, Diabetes, and COMPAS | average mean expected reward | Helped |
| Increase uncertainty in the cost evaluation | BwOUCB compared with LinUCB · Credit, Diabetes, and COMPAS | average improvement | Helped |
| Increase uncertainty in the cost evaluation | BwOUCB compared with LinUCB · Credit, Diabetes, and COMPAS | average cost | Mixed |
Surprising findings
- Under noisy cost evaluation, BwOUCB's performance was close to or better than LinUCB as noise increased, despite not using the executing probability.
Limitations
- Long feedback delays may leave insufficient data for early rounds.
- Assumes users fully execute suggested actions and the classifier is fixed.
- LinUCB regret bound depends on total number of arms K, and BwOUCB lacks theoretical guarantees.
Experimental setup
Datasets: Credit Diabetes COMPAS
Benchmarks: Credit Diabetes COMPAS
Metrics: average improvement average cost mean expected reward
Baselines: ProtoAR TAP (trustworthy actionable perturbation)
Builds on: LinUCB OTFLinUCB (contextual linear bandit with stochastic delayed feedback) GP-UCB-SDF BwO forest Algorithmic recourse (Ustun et al., 2019)
Closest papers by meaning
- Improvement-Focused Causal Recourse (ICR) (AAAI 2023 · similarity 0.88)
- Towards Robust and Reliable Algorithmic Recourse (NeurIPS 2021 · similarity 0.86)
- SafeAR: Safe Algorithmic Recourse by Risk-Aware Policies (AAAI 2024 · similarity 0.85)
- Efficient Contextual Bandits with Uninformed Feedback Graphs (ICML 2024 · similarity 0.85)
- MultiScale Contextual Bandits for Long Term Objectives (NeurIPS 2025 · similarity 0.84)
- From Search to Sampling: Generative Models for Robust Algorithmic Recourse (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.