Reproduce “Discounted Online Convex Optimization: Uniform Regret Across a Continuous Interval” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Wenhao Yang, Sifan Yang, Lijun Zhang

This paper introduces a novel Smoothed Online Gradient Descent (SOGD) algorithm that enables online convex optimization to adapt to an unknown discount factor in non-stationary environments. The algorithm provides uniform discounted regret guarantees of O(sqrt(log T / (1-lambda))) across a continuous range of possible discount factor values.

Key insights

  • Online Gradient Descent (OGD) can achieve optimal O(1/sqrt(1-lambda)) discounted regret when the discount factor "lambda" is known and its step size is appropriately tuned.
  • The Discounted-Normal-Predictor with conservative updating (DNP-cu) meta-algorithm can successfully aggregate experts even when they are optimized for different discounted regret metrics, a critical property for this problem.
  • A hierarchical aggregation strategy, combining OGD experts with DNP-cu instances, enables adaptation across a continuous range of discount factors.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.