Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Cascading Reinforcement Learning
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.
Introduces cascading RL (MDPs where users cascade-click item lists over states) and proposes an oracle BestPerm plus CascadingVI and CascadingBPI algorithms with near-optimal regret and sample complexity independent of the number of item lists.
Problem
Cascading bandits ignore user states and state transitions, and planning over ordered item lists in a cascading MDP has combinatorial action space, causing exponential computation and sample complexity.
Approach
Shows the optimal item-list value reduces to a best-subset problem (sort by weight, include items whose weight exceeds the virtual item's weight) solvable by dynamic programming in O(Nm+N log N); uses this oracle inside optimistic value iteration that maintains estimates only per (state, item) pair, with separate variance-aware bonuses for attraction probability and future value.
Key results
- CascadingVI achieves regret Õ(H√(HSNK)), matching the cascading bandit optimal bound when S=H=1 and matching the classic RL lower bound up to √H.
- CascadingBPI achieves sample complexity Õ(H^3SN/ε^2) that is independent of the number of item lists and near-optimal up to a factor of H when ε < H/S^2.
- In experiments, CascadingVI has lowest regret and fast running time versus AdaptVI, whose cost grows with the number of item lists.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use CascadingVI instead of AdaptVI | cascading RL · MovieLens | regret | Helped |
| use CascadingVI instead of CascadingVI-Oracle (ablation) | CascadingVI · MovieLens | regret | No clear effect |
| use BestPerm instead of naive exhaustive search (ablation) | CascadingVI · MovieLens | running time | Helped |
| use the variance-aware attraction-probability bonus instead of a variance-unaware bonus (ablation) | CascadingVI · MovieLens | regret | Helped |
| use the variance-aware attraction-probability bonus instead of a variance-unaware bonus (ablation) | CascadingVI · MovieLens | running time | No clear effect |
| use CascadingVI instead of AdaptVI | cascading RL · MovieLens | running time | Helped |
| use CascadingVI instead of AdaptVI | cascading RL · Synthetic cascading MDP | regret | Helped |
| use CascadingVI instead of AdaptVI | cascading RL · Synthetic cascading MDP | running time | Helped |
| use CascadingBPI instead of AdaptBPI | best policy identification in cascading RL · Synthetic cascading MDP | sample complexity | Helped |
| use CascadingBPI instead of AdaptBPI | best policy identification in cascading RL · Synthetic cascading MDP | running time | Helped |
Limitations
- Regret has an extra sqrt(H) gap to the lower bound, left open.
- Tabular setting only, requires small state space S.
- Sample complexity for BPI is near-optimal only when epsilon is small (epsilon < H/S^2).
Experimental setup
Datasets: MovieLens
Benchmarks: MovieLens (cascading RL simulation) synthetic layered cascading MDP
Metrics: cumulative regret running time sample complexity
Baselines: AdaptVI CascadingVI-Oracle CascadingVI-Bonus AdaptBPI
Builds on: UCB-VI cascading bandits variance-aware cascading bandits
Closest papers by meaning
- Contextual Combinatorial Cascading Bandits (ICML 2016 · similarity 0.92)
- True Impact of Cascade Length in Contextual Cascading Bandits (NeurIPS 2025 · similarity 0.90)
- Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation (ICLR 2024 · similarity 0.87)
- Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users (AAAI 2024 · similarity 0.86)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.85)
- On the Unexpected Effectiveness of Reinforcement Learning for Sequential Recommendation (ICML 2024 · similarity 0.85)
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.