Learning-Augmented Algorithms

Follow this topic Ask about this topic

Recent momentum

-28%

13 papers in the last 28 days · 0.2% of indexed attention

Twelve weeks of publication activity for this topic as it is defined today.

Weekly history

Recent digests

What was published in this topic, kept on the site without email delivery.

Period ending 2026-09-21

5 new papers

A weekly snapshot of new work published in Learning-Augmented Algorithms.

Period ending 2026-09-14

3 new papers

A weekly snapshot of new work published in Learning-Augmented Algorithms.

Period ending 2026-09-07

2 new papers

A weekly snapshot of new work published in Learning-Augmented Algorithms.

144 papers

Latest in Learning-Augmented Algorithms

Browse all topics →

On-line Learning in Tree MDPs by Treating Policies as Bandit Arms
May 6, 2026Anvay Shah, Ramsundar Anandanarayanan, Sharayu Moharir +1Markov Decision Processes Bandits
Order-based Rehearsal Learning
May 6, 2026Yu-Xuan Tao, Tian-Zuo Wang, Zhi-Hua ZhouSequential Decision Making Learning-Augmented Algorithms
OCRR: A Benchmark for Online Correction Recovery under Distribution Shift
May 4, 2026Adrian GrassiCorrection Learning-Augmented Algorithms
Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithms
May 3, 2026Tian Xu, Zhilong Zhang, Zexuan Chen +3Imitation Learning Learning-Augmented Algorithms
Machine Learning-Augmented Acceleration of Iterative Ptychographic Reconstruction
May 1, 2026Bowen Zheng, Katayun Kamdin, David Shapiro +10Image Reconstruction Beamline
Pessimism-Free Offline Learning in General-Sum Games via KL Regularization
Apr 30, 2026Claire Chen, Yuheng ZhangKullback-Leibler Regularization Offline Reinforcement Learning
Online semi-supervised perception: Real-time learning without explicit feedback
Apr 30, 2026Branislav Kveton, Michal Valko, Matthai Phillipose +1Semi-Supervised Learning Learning-Augmented Algorithms
Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
Apr 29, 2026Wen-Han Hsieh, Ya-Chun LiangLearning-Augmented Algorithms Stochastic Delays
Reference-Augmented Learning for Precise Tracking Policy of Tendon-Driven Continuum Robots
Apr 28, 2026Ziqing Zou, Ke Qiu, Haojian Lu +2Soft Robots Learning-Augmented Algorithms
Inference of Online Newton Methods with Nesterov's Accelerated Sketching
Apr 25, 2026Haoxuan Wang, Xinchen Du, Sen NaNewton Learning-Augmented Algorithms
Probably Approximately Consensus: On the Learning Theory of Finding Common Ground
Apr 23, 2026Carter Blair, Ben Armstrong, Shiri Alouf-Heffetz +2Consensus Deliberation
FedSEA: Achieving Benefit of Parallelization in Federated Online Learning
Apr 21, 2026Harekrushna Sahu, Pratik Jawanpuria, Pranay SharmaFederated Learning Federated Reinforcement Learning
APEX-EM: Non-Parametric Online Learning for Autonomous Agents via Structured Procedural-Episodic Experience Replay
Mar 31, 2026Pratyay Banerjee, Masud Moshtaghi, Ankit ChadhaSubstantial Memory Learning-Augmented Algorithms
Online Learning for Dynamic Constellation Topologies
Mar 26, 2026João Norberto, Ricardo Ferreira, Cláudia SoaresSatellite Networked Systems
Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization
Mar 13, 2026Noel Smith, Andrzej RuszczynskiStochastic Optimization Learning-Augmented Algorithms
Non-Stationary Functional Bilevel Optimization
Jan 21, 2026Jason Bohne, Ieva Petrulionyte, Michael Arbel +2Bilevel Optimization Learning-Augmented Algorithms
Auto-exploration for online reinforcement learning
Dec 6, 2025Caleb Ju, Guanghui LanExploration-Exploitation Dilemma Deep Reinforcement Learning
Distributed Dynamic Associative Memory via Online Convex Optimization
Nov 28, 2025Bowen Wang, Matteo Zecchin, Osvaldo SimeoneDense Associative Memory Learning-Augmented Algorithms
Are Current Continual Learning Methods Truly Agnostic? Introducing OPRE, a Step Toward Agnostic Continual Learning
Nov 11, 2025Raphaël Bayle, Martial Mermillod, Robert M. FrenchEfficient Continual Learning Continual Learning Methods
Primal-dual algorithm for contextual stochastic combinatorial optimization
May 7, 2025Louis Bouvier, Thibault Prunet, Vincent Leclère +1Stochastic Optimization Primal-Dual Methods
PB-OEL: A Performance-Bounded Online Ensemble Learning Framework With Mixed Feedback for Real-Time Safety Assessment
Mar 19, 2025Songqiao Hu, Zeyi Liu, Lufeng Hao +2Learning-Augmented Algorithms Ensemble
Infrequent Resolving Algorithm for Online Linear Programming
Aug 1, 2024Guokai Li, Zizhuo Wang, Jingwei ZhangLearning-Augmented Algorithms O(T^Β)$ Simultaneous Regret
Semi-Bandit Learning for Monotone Stochastic Optimization
Dec 24, 2023Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan +1Linear Bandits Stochastic Optimization
Online Learning: A Modern Introduction Using Convex Optimization
Dec 31, 2019Francesco OrabonaLearning-Augmented Algorithms Convex Optimization

May 6, 2026 · cs.AIJ/K move · Enter open · S save

On-line Learning in Tree MDPs by Treating Policies as Bandit Arms

Anvay Shah, Ramsundar Anandanarayanan, Sharayu Moharir, Shivaram Kalyanakrishnan

Indian Institute of Technology Bombay · Mumbai, India

A Tree Markov Decision Problem (T-MDP) is a finite-horizon MDP with a starting state

s_{1}

, in which every state is reachable from

s_{1}

through exactly one state-action trajectory. T-MDPs arise naturally as abstractions of decision making in sequential games with perfect recall, against stationary opponents. We consider the problem of on-line learning in T-MDPs, both in the PAC and the regret-minimisation regimes. We show that well-known bandit algorithms -- \textsc{Lucb} and \textsc{Ucb} -- can be applied on T-MDPs by treating each policy as an arm. The apparent technical challenge in this approach is that the number of policies is exponential in the number of states. Our main innovation is in the design of confidence bounds based on data shared by the policies, so that the bandit algorithms can yet be implemented with polynomial memory and per-step computation. We obtain instance-dependent upper bounds on sample complexity and regret that sum a ``gap term'' from every terminal state, rather than every policy. Empirically, our algorithms consistently outperform available alternatives on a suite of hidden-information games.

Markov Decision Processes Bandits Learning-Augmented Algorithms

Open paper Ask about it PDF