# Online Sequential Decision-Making with Unknown Delays

arXiv: https://arxiv.org/abs/2402.07703 · HTML: https://mlsanity.com/paper/2402.07703/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 12 Feb 2024.

## Builds on (most cited first, 8 of 8)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Bandit Online Learning with Unknown Delays](https://mlsanity.com/paper/1807.03205/) (2018)
- [Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses](https://mlsanity.com/paper/2010.12033/) (2020)
- [Online Strongly Convex Optimization with Unknown Delays](https://mlsanity.com/paper/2103.11354/) (2021)

## Built on by (most cited first, 5 of 5)

- [Exploiting Curvature in Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2506.07595/) (2025)
- [A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees](https://mlsanity.com/paper/2602.02634/) (2026)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [Capacity-Constrained Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2606.11711/) (2026)
- [Revisiting Multi-Agent Asynchronous Online Optimization with Delays: the Strongly Convex Case](https://mlsanity.com/paper/2503.10013/) (2025)

## Abstract (arXiv)

In the field of online sequential decision-making, we address the problem with delays utilizing the framework of online convex optimization (OCO), where the feedback of a decision can arrive with an unknown delay. Unlike previous research that is limited to Euclidean norm and gradient information, we propose three families of delayed algorithms based on approximate solutions to handle different types of received feedback. Our proposed algorithms are versatile and applicable to universal norms. Specifically, we introduce a family of Follow the Delayed Regularized Leader algorithms for feedback with full information on the loss function, a family of Delayed Mirror Descent algorithms for feedback with gradient information on the loss function and a family of Simplified Delayed Mirror Descent algorithms for feedback with the value information of the loss function's gradients at corresponding decision points. For each type of algorithm, we provide corresponding regret bounds under cases of general convexity and relative strong convexity, respectively. We also demonstrate the efficiency of each algorithm under different norms through concrete examples. Furthermore, our theoretical results are consistent with the current best bounds when degenerated to standard settings.