Research map / Bandits and online learning / Online convex optimization and games
Learning-Augmented Algorithms for the Bahncard Problem
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 PFSUM, a learning-augmented Bahncard algorithm that buys a card only when both the past T-recent ticket cost and the predicted T-future cost reach the break-even threshold, with a competitive ratio analysis as a function of prediction error and experiments against SUM, PDLA, and others.
Problem
Online Bahncard (recurring rent-or-buy) problem with short-term predictions of future ticket costs, for general travel times and varied ticket prices; prior learning-augmented method required full predicted solutions under slotted time.
Approach
Purchase a Bahncard only when the past T-recent regular cost and the predicted T-future regular cost are each at least the break-even threshold gamma, using them separately rather than summed, which yields bounded robustness while keeping 2/(1+beta) consistency.
Key results
- PFSUM is 2/(1+beta)-consistent and 1/beta-robust, with competitive ratio rising smoothly from 2/(1+beta) to (4-beta)/(1+2beta) as prediction error goes from 0 to gamma.
- In experiments with beta=0.8, T=10, C=100, PFSUM outperforms the other algorithms across a wide range of perturbation probabilities and has the narrowest confidence intervals.
- On Pareto ticket prices, PFSUM rises gradually with prediction error and rarely does worse than SUM, while FSUM and SUM_w deteriorate rapidly.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use separate past-cost and predicted-future-cost purchase conditions | Bahncard online algorithm · BP$(C, \beta, T)$ | competitive ratio: $2/(1+\beta)$-consistent and $1 / \beta$-robust | Helped |
| add short-term future predictions | SUM · Commuters and occasional travelers; low perturbation probability | cost ratio to OPT | Helped |
| use separate past and predicted future costs rather than a summed condition (ablation) | SUM_w · BP$(C, \beta, T)$, adversarial predictions | robustness | Helped |
| add a past-cost purchase condition (ablation) | FSUM · BP$(C, \beta, T)$, adversarial predictions | robustness | Helped |
| use a summed past-cost and future-prediction condition (ablation) | SUM · BP$(C, \beta, T)$, perfect predictions | consistency: at least $(3-\beta)/(1+\beta)$ versus SUM's $(2-\beta)$ | Hurt |
| use predicted future cost alone (ablation) | SUM · BP$(C, \beta, T)$, perfect predictions | consistency: $2/(1+\beta)$ versus SUM's $(2-\beta)$ | Helped |
| use PFSUM instead of SUM | Bahncard algorithms · Commuters and occasional travelers; wide range of perturbation probabilities | cost ratio to OPT | Helped |
| use PFSUM instead of PDLA | Bahncard algorithms · Commuters and occasional travelers | cost ratio to OPT | Helped |
| use PFSUM instead of SRL | Bahncard algorithms · Commuters and occasional travelers, particularly with significant prediction errors | cost ratio to OPT | Helped |
| increase prediction perturbation probability | PFSUM · Pareto ticket prices | cost ratio to OPT | Hurt |
| increase prediction perturbation probability | SUM_w and FSUM · Pareto ticket prices | cost ratio to OPT | Hurt |
| increase $\lambda$ | SRL · Bahncard problem with high prediction errors | cost ratio to OPT | Helped |
Surprising findings
- PDLA generally has much higher cost ratios than PFSUM and even than the conventional SUM algorithm.
- SUM_w and FSUM have no bounded robustness, with cost ratio unbounded as the ticket price goes to zero while predictions are inflated.
Limitations
- Analysis assumes the prediction error is bounded by a maximum eta over all regular requests.
- Experiments are on synthetic instances only, with predictions generated by perturbing the true instance.
- Some proofs are only sketched and the tightness claims rely on constructed examples.
Experimental setup
Datasets: synthetic travel request sequences (commuters and occasional travelers)
Benchmarks: synthetic commuter and occasional traveler instances
Metrics: cost ratio to OPT competitive ratio as function of prediction error consistency robustness
Baselines: SUM PDLA SUM_w FSUM SRL
Builds on: SUM (deterministic Bahncard algorithm) A_gamma^w (prediction-window ski-rental algorithm) PDLA (primal-dual learning-augmented Bahncard) ski-rental learning-augmented algorithm (Algorithm 2)
Closest papers by meaning
- Learning-augmented Rent-or-Buy with a Sample (ICML 2026 · similarity 0.92)
- Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis (ICML 2023 · similarity 0.90)
- Combinatorial Ski Rental Problem: Robust and Learning-Augmented Algorithms (NeurIPS 2025 · similarity 0.90)
- Learning-Augmented Online Algorithm for Two-Level Ski-Rental Problem (AAAI 2024 · similarity 0.89)
- Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods (ICML 2024 · similarity 0.84)
- Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search (ICML 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.