论文标题
在线再生学习
Online Regenerative Learning
论文作者
论文摘要
我们研究一种在线线性编程（OLP）问题，该问题通过随机输入最大化目标函数。当随机输入遵循一些I.I.D分布时，对分析此类OLP的各种算法的性能进行了充分的研究。要问的两个主要问题是：（i）算法如果随机输入不是I.I.D而是静止的，并且（ii）如果我们知道随机输入是潮流的，那么我们如何修改算法，因此如何修改我们的算法，因此，该算法可以达到相同的效率。我们通过分析再生类型的输入类型来回答第一个问题，并表明两种流行算法的遗憾与其I.I.D同行相同的订单界定。我们讨论了线性增长的输入的背景下的第二个问题，并提出了一种趋势自适应算法。我们提供数值模拟，以说明在再生和时尚输入下算法的性能。
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.
