  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.
