# Online Regenerative Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 18 Sep 2022.

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

- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [An Improved Analysis of LP-based Control for Revenue Management](https://mlsanity.com/paper/2101.11092/) (2021)
- [How the Experts Algorithm Can Help Solve LPs Online](https://mlsanity.com/paper/1407.5298/) (2014)
- [Near-Optimal Primal-Dual Algorithms for Quantity-Based Network Revenue Management](https://mlsanity.com/paper/2011.06327/) (2020)
- [Online Resource Allocation with Stochastic Resource Consumption](https://mlsanity.com/paper/2012.07933/) (2020)
- [A Hoeffding Inequality for Finite State Markov Chains and its Applications to Markovian Bandits](https://mlsanity.com/paper/2001.01199/) (2020)
- [Non-stationary Resource Allocation Policies for Delay-constrained Video Streaming: Application to Video over Internet-of-Things-enabled Networks](https://mlsanity.com/paper/1401.0855/) (2014)
- [Scalability Evaluation of NSLP Algorithm for Solving Non-Stationary Linear Programming Problems on Cluster Computing Systems](https://mlsanity.com/paper/1709.04640/) (2017)

## Abstract (arXiv)

We study a type of Online Linear Programming (OLP) problem that maximizes the objective function with stochastic inputs. The performance of various algorithms that analyze this type of OLP is well studied when the stochastic inputs follow some i.i.d distribution. The two central questions to ask are: (i) can the algorithms achieve the same efficiency if the stochastic inputs are not i.i.d but still stationary, and (ii) how can we modify our algorithms if we know the stochastic inputs are trendy, hence not stationary. We answer the first question by analyzing a regenerative type of input and show the regrets of two popular algorithms are bounded by the same orders as their i.i.d counterparts. We discuss the second question in the context of linearly growing inputs and propose a trend-adaptive algorithm. We provide numerical simulations to illustrate the performance of our algorithms under both regenerative and trendy inputs.