Policy-Controlled Generalized Share: A General Framework with a Transformer Instantiation for Strictly Online Switching-Oracle Tracking

Hongkai Hu

cs.LGMar 30, 2026

Policy-Controlled Generalized Share: A General Framework with a Transformer Instantiation for Strictly Online Switching-Oracle Tracking

Authors: Hongkai Hu

Organizations: Antai College of Economics and Management, Shanghai Jiao Tong University

Abstract

Static regret to a single expert is often the wrong target for strictly online prediction under non-stationarity, where the best expert may switch repeatedly over time. We study Policy-Controlled Generalized Share (PCGS), a general strictly online framework in which the generalized-share recursion is fixed while the post-loss update controls are allowed to vary adaptively. Its principal instantiation in this paper is PCGS-TF, which uses a causal Transformer as an update controller: after round t finishes and the loss vector is observed, the Transformer outputs the controls that map w_t to w_{t+1} without altering the already committed decision w_t. Under admissible post-loss update controls, we obtain a pathwise weighted regret guarantee for general time-varying learning rates, and a standard dynamic-regret guarantee against any expert path with at most S switches under the constant-learning-rate specialization. Empirically, on a controlled synthetic suite with exact dynamic-programming switching-oracle evaluation, PCGS-TF attains the lowest mean dynamic regret in all seven non-stationary families, with its advantage increasing for larger expert pools. On a reproduced household-electricity benchmark, PCGS-TF also achieves the lowest normalized dynamic regret for S = 5, 10, and 20.

Figures & tables

Figure 1: Switching complexity becomes learnable. Under PCGS, switching to expert $\pi_{t+1}$ incurs $-\log(\rho_{t}q_{t}(\pi_{t+1}))$ , replacing the classical uniform-restart cost $\log K$ by a data-dependent code length $-\log q_{t}(\pi_{t+1})$ .

Family	Hedge	FixedShare	GenShare(heur)	Ours
Switch	25.70 $\pm$ 2.46	19.58 $\pm$ 0.56	19.38 $\pm$ 0.59	18.93 $\pm$ 0.64
Drift	23.71 $\pm$ 2.39	19.59 $\pm$ 0.66	19.09 $\pm$ 0.63	18.64 $\pm$ 0.70
Hetero	28.95 $\pm$ 2.12	21.36 $\pm$ 0.43	21.16 $\pm$ 0.45	20.73 $\pm$ 0.47
HeavyTail	27.04 $\pm$ 3.03	21.82 $\pm$ 0.56	21.69 $\pm$ 0.59	21.17 $\pm$ 0.68
Mix	23.09 $\pm$ 2.57	19.55 $\pm$ 0.44	19.52 $\pm$ 0.47	19.39 $\pm$ 0.53
Predictive	21.04 $\pm$ 1.85	16.86 $\pm$ 0.51	16.63 $\pm$ 0.51	16.14 $\pm$ 0.59

Table 1: Main simulation results (Dynamic Regret; mean

\pm

std over 20 sequences). Lower is better.

Figure 2: Main suite summary (mean $\pm$ std dynamic regret). PCGS improves over FixedShare and GenShare(heur) across all families.

Family	WinRate vs GenShare	WinRate vs FixedShare	AvgImprov vs GenShare	AvgImprov vs FixedShare
Adversarial	100%	100%	0.56	0.75
Drift	100%	100%	0.45	0.95
HeavyTail	100%	100%	0.52	0.65
Hetero	100%	100%	0.43	0.63
Mix	75%	80%	0.13	0.16
Predictive	100%	100%	0.49	0.72

Table 2: Win rates and average improvements of Ours over baselines (paired over 20 sequences per family).

Panel of Figure 3 — Figure 3: Mechanism evidence connecting theory to behavior. In regimes with abrupt changes, $\rho_{t}$ increases, enabling rapid reallocation; in predictive regimes, $q_{t}$ concentrates mass, reducing the effective switching complexity.

Figure 4: Heavy-tail robustness grid: mean improvement (GenShare DynRegret $-$ Ours DynRegret). Positive values indicate PCGS is better.

df $\backslash$ jump_prob	0.00	0.03	0.06
2.0	0.40	0.49	0.53
3.0	0.45	0.53	0.56
5.0	0.43	0.52	0.57

Table 3: Heavy-tail robustness grid: mean improvement (GenShare DynRegret

-

Ours DynRegret). Positive means Ours is better.

Figure 5: Scaling with $K\in\{64,256,1024\}$ . The advantage of policy-controlled restarts increases with larger expert libraries.

K	FixedShare	GenShare(heur)	Ours
64	60.95 $\pm$ 1.54	60.41 $\pm$ 1.56	59.54 $\pm$ 1.87
256	65.23 $\pm$ 1.76	64.73 $\pm$ 1.77	62.57 $\pm$ 2.05
1024	67.49 $\pm$ 2.84	66.98 $\pm$ 2.83	63.30 $\pm$ 3.47

Table 4: Scaling with large expert pools. To avoid the cost of exact DP switching-oracle computation at

K=1024

, this stress test uses the ground-truth piecewise-optimal generating path as comparator rather than

L_{T}^{\mathrm{sw}}(S)

. The values therefore illustrate the large-

K

trend but are not directly numerically comparable to Table 1 .

$S$	Hedge	FixedShare	GenShare(heur)	Ours	Rel. Gain vs GenShare
5	0.01756	0.01684	0.00813	0.00630	22.5%
10	0.01928	0.01856	0.00985	0.00802	18.6%
20	0.02144	0.02072	0.01202	0.01018	15.3%
Avg.	0.01943	0.01871	0.01000	0.00817	18.8%

Table 5: Real-data benchmark on household electricity consumption. Values are normalized dynamic regret (dynreg

/T

) against the exact DP switching oracle; lower is better. Ours achieves the best value for every switch budget

S\in\{5,10,20\}

Panel of Figure 6 — Figure 6: Reproduced real-data electricity benchmark. Across all switch budgets, Ours achieves the lowest dynreg $/T$ , and the performance ordering is stable as the oracle switch budget increases.

Online Learning

Online learning studies algorithms that update predictions or decisions from sequential feedback while controlling cumulative error or regret.

See all 132 papers

From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences
Sep 17, 2026Yibo Wang, Wenhao Yang, Sifan Yang +3Online Convex Optimization Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · School of Software Technology, Zhejiang University
Parameter-Free Dynamic Regret under Heavy-Tailed Noise
Jul 29, 2026Vaneet AggarwalOnline Convex Optimization Dynamic Regret Minimization
Purdue University
Dynamic Regret in Online Convex Optimization with Indicator Switching Costs
Sep 24, 2026Naram Mhaisen, George IosifidisOnline Convex Optimization Dynamic Regret Minimization
Faculty of Electrical Engineering, Mathematics and Computer Science TU Delft, Netherlands

Sep 17, 2026J/K move · Enter open · S save

From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

Yibo Wang, Wenhao Yang, Sifan Yang, Wei Jiang+2

State Key Laboratory for Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · School of Software Technology, Zhejiang University

Online Convex Optimization Dynamic Regret Minimization Regret Minimization

Open paper AskPDF arXiv

In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, attaining optimal bounds for strongly convex and exp-concave losses often involves intricate analysis. In this paper, we present a simple framework that reduces dynamic regret minimization to switching regret minimization. As a result, we can derive dynamic regret bounds by using off-the-shelf algorithms with switching regret guarantees. The key idea of our reduction is to construct, for any comparator sequence, an auxiliary random sequence that is unbiased at each round, with the controlled variance and a manageable number of switches. Combining this construction with suitable surrogate losses, we can decompose dynamic regret into the expected switching regret against the random sequence and its controlled variance. Theoretically, for strongly convex and exp-concave losses, we establish the

\widetilde{O}(T^{1/3}P_T^{2/3})

dynamic regret bounds, where

T

denotes the time horizon and

P_T

denotes the path-length of the comparator sequence. Moreover, for general convex losses, the same reduction also recovers the

O(\sqrt{T(1+P_T)})

dynamic regret bound. Notably, all our findings match the minimax optimal results for these three types of losses, highlighting the versatility of our proposed framework.

Abstract

Online Learning

Explore similar work

From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

Parameter-Free Dynamic Regret under Heavy-Tailed Noise

Dynamic Regret in Online Convex Optimization with Indicator Switching Costs