No Internal Regret with Non-convex Loss Functions

Dravyansh SharmaAAAI 2024 · OpenReview

Abstract

Internal regret is a measure of performance of an online learning algorithm, which measures the change in performance by substituting every occurrence of a given action $i$ by an alternative action $j$. Algorithms for minimizing internal regret are known for the finite experts setting, including a general reduction to the problem of minimizing external regret for this case. The reduction however crucially depends on the finiteness of the action space. In this work we approach the problem of minimizing internal regret for a continuous action space. For the full information setting, we show how to obtain $O(\sqrt{T})$ internal regret for the class of Lipschitz functions, as well as non-Lipschitz dispersed functions, i.e. the non-Lipschitzness may not concentrate in a small region of the action space. We also consider extensions to partial feedback settings, and again obtain sublinear internal regret. Finally we discuss applications of internal regret minimization over continuous spaces to correlated equilibria in pricing problems and auction design, as well as to data-driven hyperparameter tuning.

Introduction

In the landscape of online learning, an agent repeatedly makes decisions in an uncertain environment to minimize a cumulative loss. The standard benchmark for success is external regret, which compares the agent's performance against the single best fixed action in hindsight. However, external regret can be a coarse metric in dynamic or strategic environments.

Internal regret offers a more granular perspective. It measures the penalty incurred for not applying a specific consistent modification to one's strategy—for instance, "every time I chose action $A$, I should have chosen action $B$ instead." While algorithms for minimizing internal regret are well-established for finite action spaces (the "finite experts" setting), extending these guarantees to continuous action spaces presents significant mathematical hurdles. Specifically, standard reductions rely on finding the stationary distribution of a finite Markov chain, a process that does not naturally scale to uncountably infinite spaces. This paper bridges this gap, providing algorithms for continuous action spaces even when the loss functions are non-convex.

Problem Formulation and Continuous Internal Regret

To address continuous spaces, the research first formalizes internal regret on a continuum. It is defined as a limit: the regret associated with swapping probability mass from an $\epsilon$-ball around action $a$ to an $\epsilon$-ball around action $b$, as $\epsilon \to 0$.

The challenge is exacerbated by non-convexity. In many real-world scenarios, such as hyperparameter tuning or auction design, the loss landscape is not smooth or convex. The paper specifically addresses two classes of functions:

  1. Lipschitz-continuous functions: Smooth functions where the rate of change is bounded.
  2. Dispersed non-Lipschitz functions: Functions with discontinuities (jumps), provided these "cliffs" do not concentrate too densely in any single region of the action space.

Proposed Algorithms

The paper introduces three primary algorithmic frameworks to achieve sublinear internal regret:

1. DEPoM (Discretized Exponential Potential Minimizer)

Designed for full-information settings with Lipschitz losses, DEPoM utilizes a finite $\epsilon$-cover (a grid) of the continuous space. By applying a potential-based algorithm over this discretization, it manages the trade-off between grid density and regret growth.

2. CEPoM (Continuous Exponential Potential Minimizer)

For 1D piecewise-constant losses, CEPoM handles non-Lipschitzness by leveraging a dispersion condition. This condition ensures that the adversary cannot "trap" the learner by concentrating all discontinuities in the learner's path, allowing for sublinear regret even in the presence of jumps.

3. INTERNAL EXP3

In the bandit feedback setting—where the learner only observes the loss of the action actually played—the paper proposes INTERNAL EXP3. This algorithm uses unbiased inverse-probability estimators to approximate losses for unplayed actions across the domain, combined with a fixed-point constraint to stabilize the probability distribution.

Key Insights

  • Sub-logarithmic Scaling: The success of discretization hinges on the base algorithm's sensitivity to the number of experts $N$. By using an exponential potential function where regret scales sub-logarithmically with $N$, the learner can shrink the grid size $\epsilon$ significantly without causing the regret to explode.
  • Continuous Correlated Equilibria: A major contribution to game theory is the proof that if all players in a continuous game use internal regret-minimizing algorithms, their joint play converges to a correlated equilibrium. This extends a fundamental result from finite games to the continuous domain.

Results and Performance

The paper establishes rigorous upper bounds on expected internal regret across various settings, where $T$ is the number of rounds and $d$ is the dimension:

Setting Loss Type Regret Bound
Full Information Lipschitz $\tilde{O}(\sqrt{dT})$
Full Information Piecewise-Constant $O(\sqrt{T \log(KT)})$
Bandit Feedback Lipschitz $\tilde{O}(T^{\frac{d+1}{d+2}})$
Bandit Feedback Piecewise-Constant $O(T^{2/3} \text{poly}(K, \ln T))$

The author also provides an $\Omega(\sqrt{T})$ lower bound for the full information setting, proving that the $\tilde{O}(\sqrt{dT})$ algorithm is near-optimal.

Applications and Limitations

The theoretical framework is applied to data-driven hyperparameter tuning, specifically for optimizing the parameter $\rho$ in a generalized greedy Knapsack heuristic. The results demonstrate that vanishing internal regret is achievable in these complex, non-convex optimization tasks.

However, limitations remain. In the bandit setting, the regret bounds suffer from the "curse of dimensionality," with convergence slowing significantly as $d$ increases. Furthermore, while the regret bounds are theoretically tight, the computational overhead of maintaining high-density grids in high-dimensional spaces remains a practical challenge for future research.

Summary updated

Abstract

Internal regret is a measure of performance of an online learning algorithm, which measures the change in performance by substituting every occurrence of a given action i by an alternative action j. Algorithms for minimizing internal regret are known for the finite experts setting, including a general reduction to the problem of minimizing external regret for this case. The reduction however crucially depends on the finiteness of the action space. In this work we approach the problem of minimizing internal regret for a continuous action space. For the full information setting, we show how to obtain O(sqrt(T)) internal regret for the class of Lipschitz functions, as well as non-Lipschitz dispersed functions, i.e. the non-Lipschitzness may not concentrate in a small region of the action space. We also consider extensions to partial feedback settings, and again obtain sublinear internal regret. Finally we discuss applications of internal regret minimization over continuous spaces to correlated equilibria in pricing problems and auction design, as well as to data-driven hyperparameter tuning.
BibTeX
@inproceedings{sharma2024no,
  author = {Dravyansh Sharma},
  title = {{No Internal Regret with Non-convex Loss Functions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=zwVTXIEKTG},
}
Figure