When and How to Have Negative Regrets for Online Learners? Profits for Prediction Market Makers as an Example

The correspondence between an online linear timization/learning problem using Follow the Regularized Leader and a market aking problem using a duality-based cost function market maker has been extensively explored. There, the goal of regret minimization for learners corresponds to the goal of minimizing the worst-case loss for market makers, which is a common objective for prediction market making design. With the insights from online learning about designing no-regret algorithms under a “predictable” or “more regular” loss environment (e.g., specifically, low variation or low deviation), which corresponds to some patterns” of trade sequences in market making, we aim to achieve market making that furthermore guarantees profits, i.e., negative regrets, under appropriate patterns of trade sequences, which may require conditions other than those suggested by just low deviation or variation.
We propose the optimistic lazy-update online mirror descent algorithm, which can be seen as Be the Regularized Leader with the supposedly unknown current loss vector being estimated by using the “predictability” of the loss sequence. Following the
framework of regret analysis for Be the Regularized Leader, we focus on analyzing the hypothetical Be the Regularized Leader with the “known” current loss vector when in each time step, a leader is “strong” compared with the other non-minimizers
in terms of its much less current cumulative loss, the regret will be negative in this case, and the more frequent changes of leaders the more negative of the regret. If the immediately previous loss vector is an estimator of the current loss vector, the regret can stay negative whenever the estimation error is small. In addition, we propose a modified optimistic multiplicative update algorithm catching infrequent changes of “dominant experts” quickly enough to beat a fixed best expert in hindsight in
cumulative losses thereby to obtain negative regrets. The negative regret bounds of our algorithms ensure the profit bounds of our proposed prediction market makers.