Discounted Online Convex Optimization: Uniform Regret Across a Continuous Interval
Authors: Wenhao Yang
Sifan Yang
Lijun Zhang
Venue: ICLR 2026 Poster (2026)
Keywords: Online Convex Optimization
Discounted Online Learning
Adaptive Algorithms
Primary area: optimization

Abstract: Reflecting the greater significance of recent history over the distant past in non-stationary environments, $\lambda$-discounted regret has been introduced in online convex optimization (OCO) to gracefully forget past data as new information arrives. When the discount factor $\lambda$ is given, online gradient descent with an appropriate step size achieves an $O(1/\sqrt{1-\lambda})$ discounted regret. However, the value of $\lambda$ is often not predetermined in real-world scenarios. This gives rise to a significant \emph{open question}: is it possible to develop a discounted algorithm that adapts to an unknown discount factor. In this paper, we affirmatively answer this question by providing a novel analysis to demonstrate that smoothed OGD (SOGD)  achieves a uniform $O(\sqrt{\log T/1-\lambda})$ discounted regret, holding for all values of $\lambda$ across a continuous interval simultaneously. The basic idea is to maintain multiple OGD instances to handle different discount factors, and aggregate their outputs sequentially by an online prediction algorithm named as Discounted-Normal-Predictor (DNP). Our analysis reveals that DNP can combine the decisions of two experts, even when they operate on discounted regret with different discount factors.

Published as a conference paper at ICLR 2026
DISCOUNTED ONLINE CONVEX OPTIMIZATION: UNI- FORM REGRET ACROSS A CONTINUOUS INTERVAL
Wenhao Y Sifan Yang Lijun Zhang!2.
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China School of Artificial Intelligence, Nanjing University, Nanjing, China (yangwh, yangsf, zhangl j] @ @lamda n juu.ee edu.cn en
ABSTRACT
Reflecting the greater significance of recent history the distant past in non- stationary environments, X-discounted regret has been introduced in online convex optimization (OCO) gracefully forget past data new information arrives. When the discount factor À is given, online gradient descent with an appropriate step size achieves an ((1/VI-)
discounted regret. However, the value of À is often not predetermined in real-world scenarios. This gives rise significant open question: it possible to develop a discounted algorithm that adapts to an unknown discount factor. In this paper, we affirmatively answer this question by providing a novel analysis to demonstrate that smoothed OGD (SOGD) achieves a uniform O O(Vlog T/1 X) discounted regret, holding for all values of À across continuous interval simultaneously. The basic idea is maintain multiple OGD instances to handle different discount factors, and aggregate their outputs Anccounted-Normal Predictor (DNP). Our analysis reveals that DNP can combine the decisions of two experts, even when they operate on discounted regret with different factors.
sequentially by an online prediction algorithm named
INTRODUCTION
Online convex optimization (OCO) serves as a fundamental framework for online learning, effectively modeling wide range of real-world sequential prediction and decision-making problems (Hazan 2016). OCO can be viewed as a repeated game between the learner and the environment, governed by the following protocol. In each round & [T], the learner chooses a decision w; from convex domain W C R. Then, the learner suffers loss fr (w,) and observe some information about the functions, where ft W + I is chosen by the environment. To evaluate the performance of the learner, static regret is commonly used (Cesa-Bianchi & Lugosi 2006
T Regret (T) = Σ f((w.)- min Σ f((w) 1=1
T
WEW
which is defined as the difference between the cumulative loss of the online learner and that of the best decision chosen in hindsight. However, static regret is not well-suited for changing environments where the future significantly diverges from the past. To facilitate gracefully forgetting past data as new information arrives, X-discounted regret has been proposed (Freund & Hsu 2008):
I
Σ AT - min Σ (A(W) WEW
D-Regret (T,
1=1
(=1
where À E (0, is the discount factor, denoting the degree of forgetting of the past.
Although discounted regret has been explored to some extent in prediction with expert advice
(PEA) [Frennd & Hsu 2008 Chernov & Zhdanov 2010 Kapralov Panigrahy] 2010 Cesa-bianchi al. 2012 Krichene al. 2014) and games (Brown & (aandhll|20199// et 2004), discounted
OCO has been relatively underexplored in the literature. Recently, Zhang et al. (2024) studied
"Lijun Zhang is the corresponding author.

---

Published as a conference paper at ICLR 2026
Track the best obtain optimal Regret(7)
Meto algoriciam
Maw Σ Emmmn
Expert
Expect
Expert
frlw.)) Σ f(w]
with
with
with 18l
algorteiam
Σ (-WWen) luol
Peport
Expest
A
with
with Aor
Figure I: A meta-expert framework for OCO that adapts to unknown parameters (previous work, upper panel) and discounted OCO (our setting, lower panel). Previous work typically decomposes the regret into the sum of meta-regret and expert-regret, where Wi,i denotes the decision of the i-th expert. However, this method fails to combine these experts' decisions under discounted OCO.
discounted OCO with given discount factors, aiming to establish gradient-adaptive regret bounds. For fixed factor, they derive an O(1/VI- X²) result for X-discounted regret, but their algorithm requires the prior knowledge of discount factor X. However, in many maaking problems, the discount factor reflects intrinsic dynamics rather than a tunable hyperparameter. For instance, in intertemporal economic models, the discount factor represents agents' preferences, which are shaped by empirical observations of market behavior and validated through economic studies (Cohen et al.) 2020). Crucially, in such models the discount factor is treated as a genuine parameter grounded in economic reality rather than an arbitrary design choice. This highlights the existence of a "true" discount factor that inherently resides in actual contexts, rather than freely specified in advance. Recognizing the considerable significance of adapting to an unknown discount factor in practical scenarios, Zhang al. (2024) explicitly leave this important open question in their work.
Notably, there exists a similar performance measurement for dealing with changing environments, known adaptive regret. Formally, the adaptive regret is defined as the maximal static regret for every interval [r, 8] C [7) over the whole time horizon:
s+--1
34--
SA (T-Regret(T.r)
max
Σ f((w)) min WEW
Σ fc(w)
[8,5-T EIT
where 7 is the interval length. It is evident that adaptive regret serves similar purpose to that of discounted regret, as both effectively define temporal horizon of interest. Specifically, the length of an interval in adaptive regret is conceptually analogous to the effective window size controlled by discount factor, for instance, smaller discount factor emphasizes recent data by promoting more rapid forgetting of the past, which corresponds to focus more recent intervals. The best-known algorithm (Jun et al. 2017) achieves ((vr log T') strongly adaptive regret for all interval length. Compared to the minimax optimal result for static regret, their bound incurs additional log T term, which is the necessary cost of adaptivity across all intervals. Since existing algorithms for adaptive regret (Hazan & Seshadhri] 2007 Jun al. 2017 Zhang al., 2018b Wan et al. 2022 Wang et al., 2024; Yang et al.] (0024) provide guarantees that hold simulraneously for all intervals, is natural to ask whether is possible design discounted OCO algorithm that adapts an unknown discount factor. In this paper, we provide an affirmative answer.
1.1 TECHNICAL CHALLENGE
In the literature, extensive research has explored online algorithms that adapt to unknown param- eters, including universal OCO (van Erven & Koolen, 2016: Zhang et al., 2022b 2025), dynamic regret (Zhang et al. 2018 Baby & Wang 2021 Zhao et al. 2024), and adaptive regret (Daniely et al.) 2015 Jun et al. 2017). These methods adopt the meta-expert framework shown in the upper panel of Figure I where they maintain multiple experts with different configurations and deploy a meta- algorithm to track the best one. Therefore, adapt an unknown discount factor, straightforward idea is to apply this meta-expert framework by constructing multiple OGD instances, each operating with different potential discount factor, and then using a meta-algorithm to combine their decisions.
2

---

Published as a conference paper at ICLR 2026
DNP-sn with Ay 1/7
DNN--CU with 2/T
(15)
DNP-en with
1/T (13)
(14)
(14)
Aug' Dacelme
OGD with
OGD with 2/2
OGD with
Figure 2: Overall procedure of our method: sequentially aggregation by DNP-cu with different discount factors (red nodes) of OGD experts (blue nodes), using meta-regret from (13) and (1).
However, this strategy fails to handle the discounted scenario, because existing meta- algorithmss used in the these studies, such as Hedge (Freund & Schapire, 1997) or Fixed-Share (Herbster & Warmuth, 1998), typically require that experts and the meta-algorithm operate under a unified performance measurement. For discounted OCO, the fact that the uncertainty of the discount factor is tied to the performance measurement makes this requirement difficult to satisfy. As depicted in the lower panel of Figure []] experts configured for different discount factors essentially operating under different performance measures, i.e., X-discounted regret with varying A. This renders the traditional meta-expert framework incapable of effectively handling an unknown discount factor.
1.2
OUR SOLUTION AND CONTRIBUTIONS
To address the above challenge. we revisit Smoothed OGD (SOGD) (Zhang et al. 2022a), which is proposed to support the adaptive regret for smoothed OCO. The key idea of their work to construct multiple instances of OGD with different step sizes, and employ Riscounted-Nomall.. Panigrahy, 2010; 201T) as the meta-algorithm to sequentially aggregate their decisions. Following this idea, we first discretize the continuous interval minimal window length,
with
conservative updating (DNP-cu) (Kapralov
of potential discount factors, say À E [1 1/T, 1 1/T] where by constructing geometric series to cover the range of their values. For each possible discount factor X; we create an expert by running an instance of OGD to achieve optimal Az-discounted regret. Then, employ multiple instances of DNP-cu with different discount factors p; X, to sequentially aggregate decisions from each expert. The overall procedure is illustrated in Figure 2 In this work, analyze the performance of DNP-cu under the discounted payoff setting, demonstrating its ability to effectively control the discounted regret. Furthermore, our novel analysis reveals that DNP-cu able successfully aggregate the decisions of two experts, even when they operate on discounted regret with different discount factors. Significantly, we prove that this approach achieves a uniform O( O[ylog //o X) bound for X-discounted regret that holds simultaneously for all e 1/T, - I/T), and does not require knowing the value of X.
Finally, we would like to emphasize that although the idea of deriving uniform discounted regret across a continuous interval has appeared in Kapralov & Panigrahy| (2010), their analysis conducted in the setting of PEA rather than OCO. Moreover, Kapralov & Panigrahy (2010) $ 5) only outlined the proof sketch without providing many of the technical details. Reconstructing the complete argument and addressing the gaps and inaccuracies in their presentation requires significant effort. More discussion on our technical contribution can be found in Appendix C
RELATED WORKS
In this section, we review related works to our paper, including discounted online learning, online convex optimization with memory and discounted-normal-pedccee
2.1 DISCOUNTED ONLINE LEARNING
Due to the fact that recent information is often more important than past history in non-stationary environments, discounted online learning has been proposed gradually forget the past data
3

---

Published as a conference paper at ICLR 2026
Algorithm 1 Discounted-Normal-
Require: Two parameters: p and Z
1: Set 21 0
2: for .,..,, do
3: Predict g(xz)
4: Receive by
5: Set 2++1 patt + be
6: end for
arrives. Under the setting of PEA, discounted regret is defined as (Cesa-Bianchi & Lugosi 2006
T
T Σ Bp Te.
Σ BT -p!
min PEAN
where P: is a weight picked from simplex AN {B,)_= is decreasing sequence of discount factors and is the number of experts. The X-discounted regret ① studied our work can be viewed as special case of (2), also referred to as exponential discounting. The seminal work of Freund & Hsu (208)) proposes discounted variant of Hedge, which achieves an O( In N/NN11 A)) regret bound. Subsequent works (Chernov & Zhdanov] 2 Cesa-bianchi et al. 2012: Krichene et al.)
2014) have also explored other discounted variants under the framework of "tracking the best expert". Furthermore, Brrwnn & Sandholm (2019); Xu et al. (2024) propose discounted version of counterfactual regret minimization (CFR) for solving imperfect-infomaatee
games. Recently, discounted regret has gained attention in the context of OCO. Zhang et al. (2024) investigate adaptive OGD and FTRL for discounted regret with timevvarying factors. For online linear regression, Jacobssn & Cutkosky (2024) present discounted variant of the VAW forecaster, which enjoys dynamic regret guarantees. Furthermore. they also explore strongly adaptive regret. Based on online-to-non cor--tttooo--o-eeee conversion (Cutkosky et al. 2023), Ahn et al. (2024) investigate Adam optimizer, and propose conversion from the discounted regret to the dynamic regret. This coversion is recently refined by Xie et al. (2066). However, these aforementioned works cannot adapt to an unknown discount factor.
Pegression.Dacoosen
2.2 ONLINE CONVEX OPTIMIZATION WITH MEMORY
Online convex optimization (OCO) with memory related line of work to discouted OCO. Anava et al. (2015) extend classical OCO to OCO with finite memory framework, that allows the current loss depend on constant number of past decisions. Subsequently, /umarr et al. (2023) introduces OCO with unbounded memory, which can capture the complete long-term dependence of current losses on past decisions and model complex temporal-structure applications (Agarwal et al. (019)) Specifically, to evaluate the performance of an algorithm A, they define the policy regret as the measurement Arora et al. (2012):
T
P-Regret = Σ fe
min WEW
Σ fo
Σ
A Bw
where the history space h4 E is defined as h4 Ah4-1 + Bw,, and A and linear operators. Their work considers special case with p-discounted infinite memory, where the operators are defined as A(yo. V1. ...) (0, piyo PYl, ...) and B(x) (z., In this manner, the history becomes h4 (Wr, 11, p";; ...), which places greater emphasis on recent actions while diminishing the influence of actions taken further in the past. Along this line of research, several
follow-up works have investigated various problems under the setting of OCO with memory (Zhao ctt al. 2023 Shi et al. 2020 Lin et al. 2023).
The difference between discounted OCO and OCO with memory lies in the fundamentally different ways in which past losses are incorporated. In discounted OCO, the discount factor is applied directly to the final loss function and is tied to the performance measure. In contrast, OCO with memory integrates the entire history of decisions, and the extent of historical influence is determined by the size of the memory window.
4

---

Published as a conference paper at ICLR 2026
2.3 SERIUNNNED--OMML-PPEEERRR
Discounted- -ortieedd---aal---a Preeiictr (DNP) (Kapralov & Panigrahy 2010) was introduced to solve the bit prediction problem, with its protocol described as follows. Consider an adversarial sequence of bits bi,..., by where each by E [-1, 1] can take real values, and our goal is to predict the next bit from the previous bits. each round E [T], the learner predicts confidence & [-1,, 1]. and observes the value of b,- Then, the learner gets payoff Cbb, at each round. For a -roundd game, the goal of the learner is to maximize the cumulative payoff Σi= C,b,-
The overall procedure of DNP is summarized in Algorithm In each round t. DNP maintains a discounted deviation defined as I₁ = أ p p'-1- where the discount factor p 1 - 1/n and > O is parameter for the interval length. In Step 3, DNP predicts the confidence level g by confidence function g(-), which is defined
|x] 4 4/n
2² e1on,
(x)) = sign(x) min 7 .zen erf
(3)
where Z > 0 is parameter, and cr)()) = 3/4 So e e-s ds is the error function. For any Z S 1/e, Kapralov & Panigrahy (2010) Theorem 14) have proved that DNP satisfies
Σ g(,,)b,
Σ by
(4)
T in Algorithm Compared to the strategy that predicts the majority bit with payoff E, byl. DNP achieves an O( VoVTloo T') regret by setting Z = o(1/T), as well as subconstant o( loss. Furthermore, DNP can combine the decisions of two experts by defining b as the difference between the losses of experts and restricting e E [0, 1]. For the general case of N experts, can multiple DNP to aggregate experts' decisions one by one.
where we
Kapralov & Panigrahy 2010 Lemma 18) also investigate the discounted payoff Σ pTbb and propose a conservative updating rule to control the value of the deviation Vt. To be specific, Line 5 of Algorithm iis replaced by
if [x (n)) or g( )b, < then Set T++1 pT; + bt else
Set 0++1 pTz end
where (nn) O( / log(1/2)) is constant such that g(x) = 1 for |x| 2 Un). It can be seen that the current bit be is utilized update x; only when the confidence of the algorithm is low the algorithm predicts incorrectly. Then, they demonstrate that the discounted payoff is on the order of O(-2/(11 p)) (Kapralov & Panigrahy 2010 Lemma 18). Similarly, Discounted-Norme with conservative updating can be applied to the problem of PEA.
Following their work, Daniely & Mansour (019) refine the analysis of DNP to support the switching cost and the adaptive regret. They slightly modify the confidence function as
In V orf
g(x) oo [+))] g(x)
V8n
where 11 denotes the projection operation onto the set [0, 1]. and the error function is redefined
as (r) _-e e =-2 Daniely & Mansour 2019 Theorem 10) demonstrates that their refined DNP with projection operation attains similar regret bounds to that of (4) even in the presence of switching costs. Moreover, they also establish adaptive regret guarantee. Subsequently, Zhang et al. (2022a) analyze the performance of DNP with conservative updating (DNP-cu) in the context of OCO, and propose Smoothed OGD (SOGD) algorithm, where multiple instances of OGD with different step sizes created and aggregated sequentially using DNP-cu. Their analysis shows that SOGD achieves nearly-optimal bounds for adaptive regret and dynamic regret, in the presence of switching cost. However, both of their studies do not consider discounted regret.
5

---

Published as a conference paper at ICLR 2026
3 MAIN RESULTS
In this section, we introduce standard assumptions of OCO, followed by the discounted algorithmss, including OGD and Smoothed OGD (SOGD).
3.1 PRELIMINARIES
We introduce the following common assumptions for OCO (Shalev-Shware 201
Assumption 1. All the functions ft 's's are convex the domain W. Assumption 2. The gradients of all functions are bounded by G. i.e.
max
V ((()]l S G, VI V [T].
(6)
WEW
Assumption 3. The diameter of the domain W is bounded by D, Le.,
||w w'll D. w. w.w'EW
Without loss of generality, we assume (Zhang et al. 2022a
Se(w) E [0, GD) Vw E W, LE
(8)
3.2 ONLINE GR ADIENT DESCENT FOR DISCOUNTED OCO
We investigate online gradient descent (OGD) with constant step size (Zinkevich 2003) for discounted OCO. OGD performs gradient descent to update the current solution w,:
W s++1 -llw W: - v fe(w)]
(9)
where >> O is the step size, and Tw denotes the projection onto W. In the following, we present the discounted regret OGD. Theorem 1. Under Assumptions and for any E W, OGD satisfies
f(()) Σ XT (((w) DGV2
Σ
VI-X
where we set 1) 2(1--12211111111 X)/G.
Remark: Theorem shows that OGD achieves an O(1/vI A) bound for X-discounted regret, which is on the same order as 011vV1- X²) established by Zhang et al. (2024 Theorem 6) because 1- < 1 2² 2(1 A). is worth mentioning that both the step size and the upper bound are independent of the total iterations T, thus the O(I/VI- A) bound holds uniformly over time.
3.3 UNIFORM DISCOUNTED REGRET ACROSS CONTINUOUS INTERVAL.
In this subsection, focus on the more challenging with unknown discount factor. We begin by discussing the range of À values that are of interest. With a discount factor 0 < À < 1, the effective window size is essentially --X- For T-round game, it is natural to require
[T,
where minimal window length introduced for technical reasons, implying
1 1
A
(10)
T
While there is no particular reason to avoid setting the upper bound of À to - 1/7a for some 2 1, we focus T/ for simplicity.

---

Published as a conference paper at ICLR 2026
Algorithm 2 Discounted-Normal-Pee Predictor with conservative updating (DNP-cu)
Require: Two parameters: p and Z
1: Set 21 = 0, n = 1/(1 p), and (n) = (1)
2: for tt 1..... T do
3: Predict g(x²) where g(-) is defined in 5
4: Receive b,
5: if Ir E [0, (n)) or < 0&b; > Oor > Un){bb < 0 then
6: Set rt+1 = p.z + bt
7: else
8: Set I++1 = p
9: end if
10:
end for
As shown in Theorem D OGD with suitable step size can minimize the discounted regret for particular value of A. In order to handle all possible values of À in (10). we discretize the interval
[1 1/7, 1 1 by introducing the following set:
s 1 T
2
2
T
where N loga
(11)
T
which covers the range of discount factor values. Then, for each discount factor A = 1-2i-1/T E S, we create an instance of OGD, denoted by A,. According Theorem the step size of A, set as
7/8 D 2
2 2
D
GVT
(12)
G
so that achieves the optimal d-discouneed regret. As discussed in Section 1.1 the traditional meta-expert framework is unable to combine these experts' decisions to attain optimal X-discounted regret with an unknown A. To address this issue, we choose Discounted-Norman Normall-reedittor with conservative updating (DNP-cu) (Kapralov & Panigrahy 2010) (summarized in Algorithm 2 as the meta-algorithm to sequentially aggregate the decisions from these multiple experts.
Before describing the specific algorithm, first present the performance of DNP-cu (i.e., Algo- rithm 2) under the discounted payoff setting. Although Zhang et al.) (2022a) Theorem 1) have investigated the properties of DNP-cu, their analysis is restricted the standard payoff..
Theorem 2. Suppose Z < e' n 2 max(8e, 16log } and (n) 2 22. For any bit sequence bi....,by by where |be| 1, and any nj 2 p = 1 1/n, the discounted payoff of Algorithm 2 satisfies
T
Z
T gx)))b 2 2(1 - nn)
(13)
Furthermore, also satisfies
T
Z
Σ
T
g
((xz)b;
2
p
T-b,
U(n)
(14)
2(1 - p)
1=1
where
= 1
16n z
(15)
Remark: Theorem indicates that DNP-cu effectively control the discounted payoff. First.
(14) shows that DNP-cu is able to support the X-discounted payoff when = A. Furthermore, (13)
reveals that while DNP-cu operates with discount factor p. also provide discounted payoff
guarantee for a different discount factor 7,, provided that r) 2 p. Therefore, we can exploit (13)
and (14) enable aggregation of two experts operating under the discounted regret with different discount factors, as specified below.
Algorithm 3 referred to Combiner, serves meta-algorithm aggregate the outputs of two OGD experts. Let A₁ and Ag denote two OGD algorithm, and let w and Wa2 be their respective predictions round t. Combiner generates convex combination of We,1 and Wa,2 2 as its output:
W; (1 Wt,1 W Wt.2
(16)
7

---

Published as a conference paper at ICLR 2026
Algorithm 3 Combiner
Require: Two parameters: p and Z
Require: Two algorithms: A₁ and Ag
Let DD be an instance of DNP-cu, i.e. Algorithm with parameter p and
2: Receive W1,1 and W1,2 from A1 and A2 respectively
3: Receive the prediction w1 from D
4: for 11 , do
5: Predict w, = (1 -1- wi) We.1 + w,2
6: Send the loss function fc(-) to A and A
7: Receive Wt+1.1 and W1+1,2 from A₁ and Ag respectively
8: Send the real bit f (fe(W..) - f((W.:2)/GGD to D
9: Receive the prediction W1-1 from D
10: end for
where the weight We [0, 1). By the convexity of ft(-), we have
fw:) s (1 (w..)) (
(17)
Summing (17 over Σi=1 XT- and rearranging the terms, the \1, Ay-discounted regret of Combiner with respect to A1 and A2 can be bounded follows:
x fe(ws)
Σ
S-GD
5-
Σ
x r- -'wles
(18)
1=1
T
Σ - - Σ Σ 2/2 (e(w:)
X2 - (wrle - Ce)
(19)
where we define
fe(We,1) fo (w,2))
1].
(20)
GD
To determine the weight, we pass le DNP-cu and set w. its output. By the theoretical guarantee
of DNP-cu in Theorem we can use (13) and (14) to upper bound the discounted regret (18) and (19).
respectively. Notably, since the discounted payoff (3) Theorempssupee Supportss arbitrary discount factor
p. we are able to successfully aggregate the decisions of two experts for different discounted
regret measurements. Specifically, let A₁ and A be OGD algorithms for discount factors Å₁ and X2
respectively, with w,,1 and Wx,2 as their decisions. To combine their decisions, we employ DNP-cu with p = X2 to obtain:
T
-T(w)((w))
Σ
T
XT fe(wa))
GDZ
2(1 -1)
1=1
T
Σ
fa(w)
Σ
X
(((We2)
GD
2(1 - ((1) + (n)) +
Z
1=1
t=1
where W, is the combined output of Wt,1 and Wa2, and we require 17 = A1 2 A by Theorem
Remark: By setting Z = 1/T, DNP-cu delivers small meta-regret with respect the decision from A₁ and A2. Combining the above inequalities with the corresponding Ay-discounted regret achieved by the i-th expert, we demonstrate that when the discount factor À E {A1, A2), our method can achieve the optimal O (1(1/(1 - X]) bound for X-discounted regret without requiring knowledge of the exact value of the discount factor.
To establish uniform discounted regret over the range of discount factors specified (0). we construct multiple experts by running OGD with different step sizes in (II), and apply Combiner to sequentially aggregate these algorithms. For each E [N + 1), we create an instance of Combiner, denoted by B,, to combine B;-1 and A,, where the discount factor of B; is set to X; matching that of A.. Initially, we set Bn as any baseline, such as an algorithm that predicts a fixed point in W. At each round I, we sequentially run BI.... BN+1 for step each, and output the solution of
8

---

Published as a conference paper at ICLR 2026
Algorithm 4 Smoothed OGD (SOGD)
Require: Two parameters: N and Z
1: Set Bo be any baseline
2: for N, N + 1 do
3: Let A; be an instance of OGD with step size 1/=
= 2 2
4: Let B; be an instance of Combiner, i.e., Algorithm which combines Bi-1 and A, with 1 2- and Z
parameters
5: end for
6: for
do
7: Run B B sequentially for one step each
8: Output the solution of + denoted by w;
9:
end for
BN+1. It is important to construct the sequence of algorithms A./B, in descending order of their associated discount factors, as this ordering crucial for analyzing the overall discounted regret of the algorithm. Finally, we leverage a technical lemma (Kapralov & Panigrahy 2010 Lemma 20) to extend the results from a discrete set to a continuous interval. Following Zhang et al. (2022a). we
refer this algorithm as Smoothed OGD (SOGD), and summarize it in Algorithm
We have the following theoretical guarantee regarding the discounted regret of SOGD.
Theorem 3. Suppose т 2 max 16e, log and set Z 1/T. Under Assumptions for any X E [1 1/T, 1 - 1 1/T], Algorithm satisfies
2 and
Σ x f((w))
Σ x f(() V1 - (4VlogT +
2GD
GD(N + + 2GD
(1 X)T
for any w E W, where N [log2 I1- +
Remark:
Theorem shows that SOGD achieves an O log ( bound for X-discounted regret, holding simultaneousty for all X [1 1/7, 1/T]. Compared the O (1/V1 X) guarantee Theorem I for a known discount factor X, this bound incurs an additional O(Vlog T) factor, reflecting the cost of adaptivity to the discount factor. We emphasize that this additional term is fundamental, as existing algorithms for adaptive regret also incur such log T term (see Appendix B
EXPERIMENT
In this section, we conduct empirical experiments validate the effectiveness of our methods.
Setup and contenders Our experiments conducted on the ijennl dataset from LIBSVM
Data (Chang& & Lin 2011 Prokhorov 2001), and the dimension features = 22, We study an online classification problem where, at each round t [T], the learner selects model w. W. After
submitting this decision, the learner receives a mini-batch of training examples {xx 3/2 (1) )m
(6)
where each pair consists of feature vector and its label, drawn from distribution. The learner evaluates performance using a convex loss function fe (w:)), which reflects the loss incurred, and then updates the model accordingly. In this work, set the total rounds T 10000, and the online learner suffers the absolute loss. We evaluate the performance of our proposed method (SOGD) by comparing with four baselines, including OGD using tuned step size in Theorem I strongly adaptive algorithms (SAOL (Daniely et al. 2015) and SCB (Jun et al. 2017)) and a untuned variant of OGD. For fair comparison, methods are implemented under identical experimental settings.
Results We repeat the experiments for five times and evaluate the algorithms using the discounted cunulative loss with different factors ranging from 0.5 to 0.999. We report a subset of the results here, with the remaining results provided in Appendix D As illustrated in Figure our proposed SOGD algorithm achieves performance comparable to that of OGD with a specifically tuned step size. Notably, for x= 0.999 and 01.98,, both algorithms exhibit similar loss accumulation. For À 0.996.

---

Published as a conference paper at ICLR 2026
Discount factor À 0.990
Discount factor A 0.998
Discount factor A 0.996
Cumulative loss
300-
Curmlaatvv loss
150
Cunmlative loss
75
200
100-
50-
100
50
25
2000 # of iterations
4000
6000
8000 10000
2000
4000
6000
8000
10000
2000
4000
6000
8000 10000
# of iterations
# of iterations
OGD with tuneddy
SOGD
SCB
SAOL
OGD with D/2G
Figure 3: Performance comparison of discounted cumulative loss with different discount factors.
Discount factor x
0.999
Discount factor X 0.998
Discount factor A 0.996
100
80
Cumulative loss
Curuulative loss
Canulative loss
75
60
100
40
20
2000
4000 6000
8000
10000
2000
4000 # of iterations
6000
8000
10000
2000
4000
6000
8000 10000
# of iterations
of iterations
Z 2-1/(10T)
Z 1/T
10/T
Z 100/7
Figure 4: Parameter sensitivity on different choices of with different discount factors.
while OGD shows slightly lower initial loss, SOGD quickly converges to a comparable steady-state loss. Furthermore, SOGD does not require prior knowledge of X for its configuration, offering the advantage of adaptability in scenarios where the discount factor is unknown.
Parameter sensitivity We also conduct parameter sensitivity study, our proposed SOGD algorithm involves two tunable parameters, and т. We report the results for different choices of Z here, while the is provided in Appendix D As shown in Figure our empirical findings demonstrate that SOGD is not highly sensitive to the choice of within reasonable range that aligns with our theoretical results. All four variants of SOGD with different Z achieve similarly strong performance, indicating the robustness of our method.
5 CONCLUSION AND FUTURE WORK
In this paper, we study discounted OCO with discount factor X. First, we investigate OGD with constant step size, and prove that OGD with step size 17 = O X) achieves an 0(1/VI X) bound for X-discounted regret. Second, focus on the challenging case with an unknown discount factor. To establish discounted regret for all possible factors across continuous interval, we provide a novel analysis on the discounted payoff DNP-cu, and show that DNP-cu enables aggregation of two experts with different discount factors. Thus, employ DNP-cu to sequentially aggregate the decisions from experts with different configurations to achieve our goal.
There are several directions for future research. First, it is common to consider the case where the discount factor is tireingr.nng Extending our framework to the time-varying case is an important but challenging direction. Second, strongly convex or exp-concave. It remains open whether such curvature properties can be exploited to yield improved discounted regret.
obtain tighter bounds for classical OCO when the functions
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was partially supported by NSFC (U23A20382, 62361146852), and the Collaborative Innovation Center of Novel Software Technology and Industrialization.
REPRODUCIBILITY STATEMENT
The contributions of this paper are mainly theoretical. We clearly state the problem setting and all assumptions used in our analysis, and provide complete proofs of the theoretical results in the appendix. For the experimental part, we describe in detail the publicly available datasets used, as well as the experimental setup, including parameter configurations, baselines, and other implementation details. These components together ensure that both the theoretical and empirical findings of our work can be independently verified and reproduced.
REFERENCES
Jacob Abemethy, Peter L. Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games. In Proceedings of the 21st Annual Conference on Learning Theory, pp. 415-423, 2008
Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In Proceedings of the 36th International Conference on Machine Learning, pp. 111-119, 2019.
Kwangjun Ahn, Zhiyu Zhang, Yunbum Kook, and Yan Dai. Understanding Adam optimizer via online learning of updates: Adam is FTRL in disguise. In Proceedings of the 41 International Conference on Machine Learning, pp. 619-640, 2024.
Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: Price of past mistakes. In Advances in Neural Information Processing Systems, 2015.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against an adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 July 2012, 2012.
Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Proceedings of the 34th Conference on Learning Theory, pp. 359-409, 2021.
Noam Brown and Tuomas Sandholm. Solving imperfect-informaaiee games via discounted regret minimization. Proceedings of the AAAI Conference on Artificial Intelligence, pp. 1229-1836, 2019.
Nicolò Cesa-Bins Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
Nicolò Cesa-biancha Pierre Gaillard, Gabor Lugosi, and Gilles Stoltz. Mirror descent meets fixed share (and feels no regret). Advances in Neural Information Processing Systems 25, 2012.
Chih-Chunp Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM
Transactions on Intelligent Systems and Technology, 2(3):77:127:22. 2011.
Alexey Chernov and Fedor Zhdanov. Prediction with expert advice under discounted loss. In Algorithmic Learning Theory, pp. 255-269, 2010.
Jonathan Cohen, Keith Marzilli Ericson, David Laibson, and John Myles White. Measuring time preferences. Journal of Economic Literature, pp. 299-347, 2020.
Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal, stochastic, non-smooth, non-convex optimization through online-to-mee coine-tt-non-comee con-ve conversion. In Proceedings of the 40th International Conference Machine Learning, 2023.
11

---

Published as a conference paper at ICLR 2026
Amit Daniely and Yishay Mansour. Competitive ratio vs regret minimization: achieving the best of both worlds. In Proceedings of the 30th International Conference on Algorithmic Learning Theory, pp. 313-3333-3 2019.
Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In Proceedings of the 32nd International Conference on Machine Learning, pp. 1405-1411, 2015.
Yoav Freund and Daniel Hsu. A new hedging algorithm and its application to inferring latent random variables. arXiv preprint arXiv:0806. 4802, 2008.
Yoav Freund and Robert E Schapire. A
generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-13) 1997.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, (3-4):157-325, 2016.
Elad Hazan and C. Seshadhri. Adaptive algorithms for online decision problems. Electronic Colloquium on Computational Complexity, 88, 2007.
Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32(2):
151-178, 1998.
Andrew Jacobsen and Ashok Cutkosky. Online linear regression in dynamic environments via discounting. In Proceedings of the 41st International Conference on Machine Learning, pp. 21083-21120, 2024.
Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett. Improved strongly adaptive online learning using coin betting, In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 943-951, 2017.
Michael Kapralov and Rina Panigrahy. Prediction strategies without loss. arXiv:1008.3672, 2010.
ArXiv e-prints,
Michael Kapralov and Rina Panigrahy. Prediction strategies without loss. In Advances in Neural Information Processing Systems 24, pp. 828-8366 836, 2011.
Walid Krichene, Benjamin Drighès, and Alexandre Bayen. On the convergence no-regret learning in selfish routing. In Proceedings of the 31st International Conference on Machine Learning, pp.
163-171, 2014.
Raunak Kumar, Sarah Dean, and Robert Kleinberg. Online convex optimization with unbounded memory. Advances in Neural Information Processing Systems, pp. 26229-26274 2023.
Yiheng Lin, James A. Preiss, Emile Anand, Yingying Li, Yisong Yue, and Adam Wierman. Online adaptive policy selection in time-varying systems: No-regret via contractive perturbations. In Advances in Neural Information Processing Systems, pp. 13508-53521, 2023.
Erik Ordentlich and Thomas M. Cover. The cost of achieving the best portfolio in hindsight. Mathematics of Operations Research, 23(4):96-992,, 1998.
Danil Prokhorov. IJCNN 2001 neural network competition. Technical report, Ford Research Laboratory, 2001.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. Advances in Neural Information Processing Systems, pp. 20636-20644 2020.
Tim van Erven and Wouter M Koolen. MetaGrad: Multiple learning rates in online learning. In Advances in Neural Information Processing Systems 29, pp. 3666-3674, 2016.
Yuanyu Wan, Wei- Wei Tu, and Lijun Zhang. Strongly adaptive online learning over partial intervals. SCIENCE CHINA Information Sciences, 65(10))20201, 2022.
12

---

Published as a conference paper at ICLR 2026
Yibo Wang. Wenhao Yang, Wei Jiang, Shiyin Lu, Bin Wang. Haihong Tang, Yuanyu Wan, and Lijun Zhang. Non-stationary projection-fis free online learning with dynamic and adaptive regret guarantees. In Proceedings of the 38th AAAI Conference Artificial Intelligence, pp. 15671-15679, 2024.
Yan-Feng Xie, Yu-Jie Zhang, Peng Zhao, and Zhi-Hua Zhou. Dynamic regret via discounted- to-dynamic reduction with applications to curved losses and adam optimizer. arXiv preprint arXiv:2602.08372. 2026.
Hang Xu, Kai Li, Haobo Fu, QIANG FU, Junliang Xing, and Jian Cheng. Dynamic discounted counterfactual regret minimization. In The Twelfth International Conference on Learning Repre- sentations, 2024.
Wenhao Yang, Wei Jiang, Yibo Wang. Ping Yang, Yao Hu, and Lijun Zhang. Small-loss adaptive regret for online convex optimization. In Proceedings of the 41st International Conference Machine Learning, pp. 56156-56195, 2024.
Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou, Adaptive online learning in dynamic environments, In Advances in Neural Information Processing Systems 31, pp.
2018a.
Lijun Zhang, Tianbao Yang, Rong Jin, and Zui-Hua Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference Machine Learning, pp. 5882- 5891, 2018b.
Lijun Zhang, Wei Jiang, Jinfeng Yi, and Tianbao Yang. Smoothed online convex optimization based discounted-normall coreeed--nmaal-p-iicotoooo In Advances in Neural Information Processing Systems 35, pp. 2022a.
Lijun Zhang, Guanghui Wang, Jinfeng Yi, and Tianbao Yang. A simple yet universal strategy for online convex optimization. Proceedings of the 39th International Conference on Machine Learning, pp. 26605-26623, 2022b.
Lijun Zhang, Yibo Wang, Guanghui Wang, Jinfeng Yi, and Tianbao Yang. Universal online convex optimization meets second-order bounds. Journal of Machine Learning Research, 26(152):1-53, 2025.
Zhiyu Zhang, David Bombara, and Heng Yang. Discounted adaptive online learning: Towards better regularization. In Proceedings of the 41st International Conference on Machine Learning, pp. 58631-58661, 2024.
Peng Zhao, Yu-Hu Yan, Yu-Xiang Wang, and Zhi-Hua Zhou. Non-stationary online learning with memory and non-stochastic control. Journal of Machine Learning Research, pp. 1-70, 2023.
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non-stationarity: Problem- dependent dynamic regret for online convex optimization. Journal of Machine Learning Research, 25(98):1 52, 2024.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pp. 928 928-936, 2003.
13

---

Published as a conference paper at ICLR 2026
A ANALYSIS
In this section, we present the analysis of all theorems.
A.1 PROOF OF THEOREM
1
The proof is similar to that of Zhang et al. (2024, Theorem 6), except that we adopt a different step size. From Jensen's s inequality and the standard analysis of OGD, we have
T f((m)) Σ AT f((w)
XT TT(((S((W.)) We w)
T
T
1/ T
(l|w, - 1o|2-//wa ||W++1 - wwl) +
Σ
11f((w:))
21
2
1=1
T
TT AT-((-1)
! T
|1
w|1 +
Σ
|| w/1
+
x - fl((w)))l
2m
2m
2m
2 1=1
1=
D2
- D2
G
T-t +
T
21
2m
2 t=1
t=2
D2
(1
X)D2
G2
1
D
G2 DGV2
+
2m
2m
1
A
2 1 1 x
11
2(1 A) V1-X
where in the last step we set
D DV/2(1-) A)
11 =
G
A.2 PROOF OF THEOREM 2
The proof builds on the approach of Zhang et al. (2022a) Theorem 1), and we highlight the main difference below.
Following the arguments Kapralov & Panigrahy (210)) and Zhang et al. (002a)), we analyze the payoff of Algorithm@ leveraging Algorithm [ This is because the update rule of Algorithm iis simpler, making the analysis more tractable. Specifically, we construct the following bit sequence
{
be, if Line 6 of Algorithm 2 is executed at round t O, otherwise.
be =
straightforward to verify that the prediction g(xx),, as well as the deviation Vt,, generated by Algorithm 2 on the bit sequence bi...., br, is exactly the same that of Algorithm [ on the transformed sequence bi...., by. In the following, we first establish the theoretical guarantee for Algorithm on the transformed sequence and then translate this result to the payoff of Algorithm 2 on the original sequence. We establish the following theorem for the discounted payoff of Algorithm
Theorem 4. Suppose Z < 1 and n 2 max(8e, 16 log }. For any bit sequence by...., by such that [bx] < 1, and any 1) 2 p = 1 - 1/n, the discounted payoff of Algorithm 1 satisfies
Σ
T
TT
n
9( 2
n
T-t
Iig((z)
$,
(21)
n
2
2(1 - n)
where L S g(s)ds is the potential function. Furthermore,
T
T
T T-t
(z1g(x))
Z
Σ p
'"''g(00)br ggxx))b 2 Σ
T'
p
by
+
-TT41
(22)
2
2(1 p)
1=1
t=1
14

---

Published as a conference paper at ICLR 2026
From Theorem
we have
T
2 (xx)))r
2
T
11
1-
[zg(dr)
- -
Z
(23)
2
2(1 77)*
[=1
Σ
T
(xx))bb
T
bb. +
Σ
T
p--
xzg((t)
2
2(1
Z
p)
-T+1
(24)
[=l
f=1
t=1
From (38) of Zhang et al.
(0022a), we have
g(xx) (bk bτ) 2 0, by # bk:
(25)
(bx - .b) 2 by by if by + bu.
(26)
which implies
Σ
( )b, Σ
T gg0x)) +
"1 be)
t=1
(27)
25
(zig(Te)
- -
Z
2(1 11)
n
T
T
T
Σ
g(x))) C
T
bb
g(x, )bg + Σ
p² "g(x,)(b. -b))
1=1
t=1
(28)
20
T
T-t
7
bb
FT+1-
2
2(1 p)
To simplify the term involving
((g(z,) 2
Pt we make use of the following property of Algorithm
(Zhang al. 2022a (33))
-1 x S U V2
(29)
and establish the following lemma.
Lemma 1. Suppose 7 < } n 2 max (8e, 16 log 2 and U()) 2 20. Under the condition in
29
we have
z1 g(s)ds v veg(s.))
$
(30)
Finally, we obtain 13 by combining and 30 and obtain 14 by combining 28
29 and 30
A.3 PROOF OF THROREM 3
We start by presenting the discounted regret of each OGD algorithm, namely A.. Let wa,s be the
output of A, at round f, and recall that the step size is set according to (12) From Theorem I have
T Σ f((w)= < DGV2 t=1
OxT-ff(We.))
fe(wee)
(31)
VI-Ai
1
for all E W, where A, = 2 /T.
Next, we proceed to bound the discounted regret of SOGD at each discount factor X where i [N + 1]. To this end, make use of the theoretical guarantee of DNP-cu stated in Theorem 2 Note that the conditions of Theorem 2 impose lower bound on the window size n. Therefore, to apply this result, need to ensure that the minimal window size appearing in Algorithm satisfies
1 7
min <E[N+1] 1
2 max
Se, 16 log
(32)
X;
2N
Since
T
T
2N
2
+ logg
T
2
15

---

Published as a conference paper at ICLR 2026
32
holds when 2 max(16e, 32 log / J. Furthermore, also require (n)) 22 in Theorem 2
We now proceed to estimate a lower bound for Un)). Since g(z) is a monotonically increasing function on [0, (n)]], it follows that if we can find point z' such that g(x') < 1, then we must have x < (n).. Setting x = 4 Ayn, we have
V
g(4vn) V8
7 erf
e 0.8517
v2
4v2
where the last step because we set Z 1/T and Since n)) < 1, we have
S and property of the error function.
Unn) 2 A/n 2 4v 32 2 22.
Denote the output of B, round by Vt,i. and observe that the final output is w. Vt,N+1- Then, we decompose the xi-discounted regret of SOGD as
f((w)) XxT - (((eN++))
-xT-(((w))
1=1
T X T s((ee)) - (i(VAA-))
T
Σ
Σ 18-Sa((v.))
Σ
-
fe(We,s
(33)
k=
t=1
1=1
0&
1
T ff
f((w.))
where og denotes the di-discounted regret of B& with respect to B 3 denotes the Xp-discounted
regret of B, with respect to A,, and y denotes the A;-discounted regret of A,. We can directly bound y using 31 so we next focus on bounding as for k = i + I...., + 1, and B.
Recall that B& invokes DNP-cu with discount factor A to aggregate B and Ag. Define
fe( 1
GD
Following the derivation of (18). have
Ogk Xx -X -GD
Σ x
wenle,
(34)
where wi,k is the output of the k-th instance of DNP-cu at round Since the discount factors are set in descending order in Algorithm 4 it holds that
A Ae. for all k =
+ 1.
Thus, we can use 13 in Theorem 2 to upper bound the RHS of 34 yielding
GDZ
(35)
2(1 X.)
Similarly, following the derivation of
19
we have
T
T
8
T -T- f.(ve.))
Σ
f.(w.) GD Σ x-- (wi,bees -e,,)
14
Z
Z
log I
GD
+U
+1]
GD
+ 16 1- A;
+ +1)
2(1 - X1)
1- >x
2(1 - (
Z
(36)
16

---

Published as a conference paper at ICLR 2026
Substituting 31
(35
and
36
into
33
obtain
T
GD
1 + V2
GD(N + +1) 2(1 Xz)
f((w))
f(()
41
11108 log
+ GD (37)
VI A
Z
t=1
t=1
for
+1.
So far, we have established discounted regret guarantees for each discount factor A, where i E [N - 1].
Next, we extend these results to the continuous range of À values specified in (10). To this end, we make of the following lemma (Kapralov & Panigrahy| 2010 Lemma 20).
Lemma Given a sequence , 8T, and discount factor
1, define the X-smoothed average
at time T by
T
=
t=1
Then, for any X > X2. the A smssothh average at time T is convex combination of xy-smoothed average at time j S T:
(1- A1)(A - -22)
ST
X-
1- A2
ST-J
JKT
where the coefficients the RHS are nonnegative and sum to 1.
According our construction in for each X E [1 such that
11-1/T,11 1-11,1111/10 there exists index i E [N]
1/T],
2 T
2
A41 = 1
<\ s =1
T
implying
1 di+1
and
I
(38)
-
Ait1
1 1- X
1- x
From Lemma we know that
2
T
11
Σ
A
T-
(f((w) - f((w)
can be expressed as convex combination of
T
T-1
Σ
- -1((w), \st1)
Σ
T T-1-t [ [f((w) - f((w)
t=1
As result
T
(1 (1- X) Σ XT [w((w) - f((w)]
<(1 Xi+1)
max jE[T]
( fe(w)] f((w))
GD
GD + GD
A
log Z + V2
+ 2(1 A441)
/1 Ait1
where we use the fact that
37 holds for any integer T. Thus, we have
T
[f((w:) Sc(w)]
1=1
Ain1
GD
( (4/108
1
v2
GD(N 1)Z
+ GD
X
/I - Ai41
7
2(1 - -
38
2GD
| Av100 log + V2
GD(N 1)%
+2GD.
V1 - X
1-
Finally, set 7 1/T to finish the proof.
17

---

Published as a conference paper at ICLR 2026
A.4 PROOF OF THEOREM 4
The overall proof strategy is similar to that of Zhang et al. [022aa] Theorem 5), with the key distinction being that we consider the discounted payoff rather than the standard payoff. Moreover, our proof is more concise, as we focus on the interval [1, 7) and omit the switching cost. Building upon their analysis while adapting it to our setting, we directly leverage several intermediate results to avoid redundancy.
From (70) of Zhang al. (0022)) we know the difference between any two consecutive deviations is bounded by 2, i.e.,
Ft - 21+1 S 2. Let [(x)) be the indicator function of the interval [0, (u))(nn + +2]. We have (Zhang et al. 2022a (74))
(39)
max Ig' (s)) - n =E(=e
x. 24 (I)))) + Z.
(40)
We also recall the following inequality for piecewise differentiable functions f [a, b] + R Kapralov
Panigrahy 2010: Daniely & Mansour, 2019):
Se
[(x)do s [(a)(b- - a) + max ['()) (b- (b-a)²
(41)
Following the idea outlined in Kapralov & Panigrahy
2010 proof of Lemma 18), we have
1141 n = -2+11 De + (1 - 1,
g(s)ds+ + (1 1))
1
g(xe)(E(+1 - 24) + (0
2
xx)²
max aE 1(
[g'(s) (1 11-17) 17)
39
1
Σ ((zz)
--It + bb
+
max
[g((s) + (1 (1-11) 11)
(42)
1
1
+ 7
g(x2)
32
bt
+ 2n
#1g((x)[((x))
2 (1 - n))
n
=g(x=)b;+
+
(2))
(I(x)) - 1) + (1 - 1) 2n
+
2n
2
1
(x:) (1(z)) 1) + 1
④ g(g(2z) xz))
Z
Sg(xz)be
2n
2
2
where the last line follows from the condition 17 2 1/n. Then, we have
S 47+1 - -1
(0441-1(bb)
12
T
T
T
T-t
xzg((11)
Z T +
11
(x()))b
+
"1
T
x1g(2)) (I(x))- 1) +
i.
1
T-t
2n
n1
2
1=1
1=1
T
T
1
T
xig(as)
+ Z
g ((1z))
-11
-
xgg(zr)
(1(2z) - 1) +
4
2n
2(1 1)
(43)
where in the first equality we use the fact that +. 0 since 21 = 0. We proceed bound the second term the last line of (43) Combining the simple observation that
(ag(xz) (1 - T(xx))) 2 0,
with 43 we obtain
21 Recall that
T -+
ST+1
and thus
T
21 2
T
T p
T-
Z
Σ
g(
bb
-TT-I
2
2(1 p)
1=1
18

---

Published as a conference paper at ICLR 2026
g(z)
1
B
0
U(n)
Figure 5: The confidence function g(z)).
A.5 PROOF OF LEMMA 1
We note that Kapralov & Panigrahy (2010) Lemma 22) have established a similar result for their confidence function (3). but provided only incomplete proof. this paper, we adopt novel and insightful approach to provide an entirely new and complete analysis.
First, when Ie [-1, 0], we have
F1g(1e) 2
& =
0.
since y(x) = 0 for E [-1, 0J. Second, when E (m)). it follows from Daniely & Mansour (2019 Lemma 18) that (ss) is convex over 20, Therefore, (30) holds by the convexity of g(s). Third, when 2, [Unn), (n) + 1]. we have
+ I g(
/ U(n)
g(8)ds + - Un))
According to definition of g(r), we have mag(zz) when E [U(n), Un) + 1]. Accordingly, our objective reduces to proving the following inequality:
U(n)
g(s)ds + I (n))
for n, E [U(n), (n)) + 1], which implies
[ (/ g(s)ds S U()) Ft
U())
(44)
To establish that 44 holds for xs E [U(n), U()) + 11. suffices to prove the inequality for maximum value of x, in this interval, that is, when = Un)) + 1. Specifically, we need to show that
(()) L g(s)ds
Unn) -1
(45)
As long as (45) can be established, the proof of Lemma is complete. However, proving (45) remains highly challenging. To address this, we propose a novel approach that combines analytical and geometric insights. The confidence function g(x) is illustrated in Figure
Notably, identify point B (c, ((c)) on the function g(x). If we can show that the following inequality holds at this point, then (45) is immediately satisfied:
U(n) 2
g(s)ds SAOAB <
and SBOAB 2 5
From Figure it can be seen that the area of triangle 40AB equal to the sum of the areas of triangles 4OBC and AABC. Therefore, we have
1
SAOAB = BC (c U-) U(n)-g(c)
2 2
19

---

Published as a conference paper at ICLR 2026
where the point C' is (n( o(c).g(c) because this point is on the line OA: U(m].
To prove
we need to find point B (c, g())) that it satisfies
c c- Un) g(c) 2
To achieve this, we find specific point B such that Unz) 8, and we have
n
U(n) -
(U(w) 9)2
g(U(n)
8)
erf
8
v8n
T1 Z erf
(n)
(((()) a)2 16m
8
88n
64 (6
10m
(60)(m)
512
where the last two steps are due to the definition of (n) and n 2 32. Then, we find that
c U(n) x(c) = Un) 8 - Un) g(U(n) - 8)
2 (n) (1 (1-e 612
(m)
2 1.4648
where the last step is due to Unn) 2 22. We finish the proof.
B FURTHER CLARIFICATIONS ON OPTIMALITY
Compared to the theoretical guarantee of OGD Theorem SOGD incurs an additional log T factor. We emphasize that this additional term is necessary cost for adapting parameter. As discussed in our work, discounted OCO with an unknown discount factor serves a similar purpose to adaptive regret, as both effectively define a temporal horizon of interest. In fact, existing algorithms for adaptive regret (Hazan & Seshadhri 2007 Jun et al. 2017 Zhang et al. 2018b) also incur such term, in work. Specifically, several online algorithms achieve O(vT log T), O log log T), and O log 7 T)) for general convex, A-strongly convex, and a-exp-coneave functions, respectively, where r is the interval length. Compared to the minimax optimal result for static regret (Ordentlich & Cover
unknown
1998 Abernethy et al. 2008), i.e., O(VT), 0(2 log T), and 0 log 7",, it is evident that the adaptive regret bounds suffer an additional O 7) or O(log T) term, reflecting the cost of adaptivity to every interval.
C MORE DISCUSSION ON TECHNICAL CONTRIBUTIONS
In the literature, DNP-cu is not a well-studied algorithm. Kapralov Panigrahy (2010) proposed the original algorithm, but without a rigorous theoretical analysis. Subsequent works by Daniely & Mansour 2019) and Zhang et al. (2022a) have progressively improved its theoretical foundations. To adapt it to discounted OCO with an unknown factor, we need to make technical contributions to the original theoretical analysis.
we provide new theoretical guarantee (Thcorem 2) to demonstrate that DNP-cu can support X-discounted regret when the parameter p = set, and at the same time, can provide guarantee on the discounted payoff for a different discount factor, which proves the theoretical feasibility of the algorithm design. Compared to the standard payoff analysis, we show that the can be effectively bounded. Furthermore,
Specifically,
discounted payoff with different factor struggle with the potential function in Theorem 4 Bounding this potential function is particularly challenging, and previous work does not provide rigorous proof. In our work, we establish new lemma, i.c., Lemma I] by adopting a novel and insightful approach to provide an entirely new and complete analysis upper bound this function.
need to
20

---

Published as a conference paper at ICLR 2026
Discount factor À = 0.9
Discount factor ==
Discount factor A= 0.8
10
Cumulative loss
Curmlative loss
10-
Cunulativo
4
10000
2000
4000
6000
8000
10000
2000
6000 8000 10000 of iterations
# of itcrations
# of itcrations
Discount factor == 0.7
Discount factor A 0.6
Discount factor À = 0.5
Cumulative loss
Cumulative loss
Cumulative loss
2000 4000 6000
8000
10000
2000
4000
6000
8000
10000
2000
4000 of iterations
6000
8000 10000
of iterations
of iterations
OGD with tumed y)
SOGD
SCB
SAOL
OGD with v, = D/2G
Figure 6: Performance comparison of discounted cumulative loss with different discount factors.
Discount factor À 0.999
Discount factor À 0.9998
60
Discount factor 0.996
200
100
Cunulative loss
Curnlaatiee loss
Cumulativv loss
1.50
75-
40
100
550
20
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
2000
4000 of iterations
6000
8000
10000
# of iterations
# ofiterations
32ln
Sc
T= 32e
64e
Figure Parameter sensitivity on different choices of with different discount factors.
D ADDITIONAL EXPERIMENTS
Following the experimental setup in the main text, we additionally report experimental results across wide range of discount factors À {0.9, 0.85, 0.8, 0.7, 0.6, 0.5). From the definition of discounted cumulative loss Σ (T-')((w,) it is clear that as the discount factor À decreases, our algorithm places more emphasis the recent losses. As shown in Figure all algorithms quickly converge to a stable minimum loss. For all values of discount factors X. it is evident that our algorithm, SOGD, along with OGD with tuned step size, outperforms other baselines.
We also conduct experiments on different choices of r. As shown in Figure 7 the performance of SOGD does not vary significantly and converges steadily to the optimal solution. Combined with the parameter sensitivity experiments for choices of Z the main text, we recommend setting 1/T and 32 (n(1 ( 32e for practical guidelines.
21

---

Published as a conference paper at ICLR 2026
E PRACTICAL MOTIVATIONS FOR THE UNKNOWN DISCOUNT FACTOR
In many real-world applications, the discount factor À cannot be directly specified by the designer, yet selecting an appropriate "true" value is crucial for reliable decision-making. We highlight two representative scenarios where the discount factor inherently exists but is unknown in practice.
Control Systems: many control systems, including LQR and other infinite-horizon formulations, the discount factor implicitly reflects physical properties of the system, such as responsiveness, energy dissipation, degradation, and long-term stability. scenarios, this discount factor is typically determined based on system dynamies, time delays, or reliability decay. Therefore, this factor cannot be directly chosen by the designer, doing so would lead unstable controlling.
realistic
Economic Decision Modeling: In financial forecasting and portfolio optimization. the discount factor determines how rapidly past returns are devalued when assessing current market conditions. Its value is implicitly determined by latent market characteristics such as long-term dependence, autocorrelation strength, and structural stability. Thus, the discount factor is not an arbitrary design choice but an unknown parameter rooted in real market behavior, requiring careful estimation through empirical studies or behavioral assumptions.
F THE USE OF LLMS
In preparing this manuscript, we used large language models (LLMs) solely to improve the clarity and readability the writing, with the goal of helping readers better understand our ideas and methods. LLMs did not contribute to any part of the research itself, including the generation of ideas, theoretical proofs, algorithm design, or other components that constitute the core contributions of this paper.
22


Reviews:
[{"review_id": "RvWpuwDBkz", "reviewer": "Reviewer_DsSC", "summary": "The paper addresses online convex optimization (OCO) with discounted regret, where recent losses are weighted more heavily than distant ones via a discount factor $\\lambda$. Existing papers assume the discounting factor is known, whereas this manuscript considers the unknown $\\lambda$ case. The main idea is to run many instances of SOGD with a specific lambda, and then run a meta selection algorithm to aggregate the outcome.", "questions": "-\t(17) (18) are not too obvious, providing more details will help. \n\n-\tCompare theorem 3 to theorem 1, the dependence on lambda is worse. I wonder whether the bound is tight or if there are potential ways to further improve it.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Addresses a clear open problem in discounted OCO, by providing a discounted regret bound for uniform range of lambda. The learner does not know lambda a priori. \n\nThe technical challenges of the problem were clearly presented. The prior aggregation framework needed to operate under a uniform performance metric, whereas in this paper each expert has a different metric. \n\nProvide a step by step derivation on the motivation behind the algorithm design which is insightful.\n\n Provides rigorous theoretical analysis and complete proofs. Simulations are provided as well.", "weaknesses": "-\tI encourage the authors to provide **more concrete** motivations on the relevance of the problem of unknown lambda, why it is practically relevant other than the mere theoretic interest. \n-\tAs mentioned in the intro, part of the motivation is that the user’s preference might change, indicating a time-varying lambda. Can the paper be extended to the time-varying lambda case? i.e. the learner has some feedback signal that is indicative of lambda, and can adapt itself to optimize the regret with time-varying lambda?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5r79Zy81gh", "reviewer": "Reviewer_LMJ1", "summary": "The paper studies discounted online convex optimization and demonstrates that it is possible to achieve regret results for unknown bounded discount factors. It achieves this by analyzing and utilizing the existing algorithm DNP.", "questions": "Questions:\n\nPage 6 Line 301: is the effective window size the sum of the discount coefficients?\n\nPage 6 Line 305: for $\\lambda$, $\\tau$ is related to the lower-bound, while the footnote is talking about the upper-bound. Is there a mistake here?\n\nPage 8 Line 409: why $Z=1/T$, why not smaller?\n\n\nSuggestions:\n\nGive more substance to the need to use DNP as opposed to another mixture of experts algorithm.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Originality:\nThe paper creatively applies the DNP algorithm to the discounted optimization problem and remove the need to know the discount factor.\n\nQuality:\nThe submission seems technically correct. Experiments are a plus. The algorithms and the experimental settings appear reproducible.\n\nClarity:\nThe submission is clear in general.\n\nSignificance:\nTheoretical novel findings in the form of discounted regret results for unknown discount factors are obtained.", "weaknesses": "I am leaning towards rejection. Below are the reasons.\n\nUtilizing DNP-cu seems to help in arriving to a clean result, but it seems any combiner could have worked. I am not sure if the issue of different discounted performance measures as explained in Figure 1 is as great as advertised. Since the combined $\\lambda$ values have a difference of $1/T$, the regret redundancy propagating due to mismatches seems to be finite at each combination node, similar to DNP-cu.\n\nAside from that, exponentially growing step-sizes and iterative combination of experts (with intermediate experts in the mix) are established methods in the literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "353KfOU2S6", "reviewer": "Reviewer_hZvg", "summary": "The authors consider the setting of online convex optimization with $ \\lambda $-discounted regret. Prior work assumes known $ \\lambda $ and shows online gradient descent achieves $O ( (1-\\lambda)^{-\\frac12} ) $ discounted regret. In this work the authors consider the setting of \\emph{unknown} $ \\lambda $ and show that a carefully designed aggregation of online gradient descent instances can achieve $ O ( \\log T (1-\\lambda)^{-1} ) $ discounted regret for any $ \\lambda $ in a defined continuous interval.", "questions": "* Please see the weaknesses section about lack of discussion on online convex optimization with unbounded memory. Could you discuss when using one model over the other is preferable? Can their techniques be extended to $\\lambda$-discounted regret? Can your techniques be used to derive results for their model?\n\n* Can you expand a bit more on why the ordering is crucial when aggregating the difference OGD instances?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper studies an important open problem: that of achieving discounted regret bounds with an unknown $ \\lambda $. The paper does a decent job of motivating that in some settings $ \\lambda $ is truly unknown and is not just a tunable hyperparameter.\n\n* In contrast to typical aggregation mechanism in meta algorithms with multiple instances of an online gradient descent or experts algorithm, this work relies on the less well-known mechanism of discounted normal predictor with conservative updates. The authors show that this aggregator, works used in a particular order of $ \\lambda $.\n\n* The authors also provide some empirical results that reflect their theoretical findings.\n\n* The authors rely on existing algorithms (e.g., aggregation with DNP-cu was already used in Zhang et al. (2022)). However, they prove an important property of DNP-cu: that it can aggregate across different discount factors.", "weaknesses": "* There is a related line of work on online convex optimization with unbounded memory (Kumar, Dean, Kleinberg, NeurIPS 2023). One special case is $\\rho$-discounted infinite memory, where the loss in each round depends on the entire history of decisions and each past decision is weighted by a geometric factor of $\\rho$. This paper does not discuss similarities and differences from this line of work.\n\n* Algorithm 3 is hard to read - I had to keep jumping around to look at the algorithm and at the equations that it references. It would be easier for the reader if you wrote the equations inline.\n\n* Since the algorithm is the same in Zhang et al. (2022) but you prove an additional property of DNP-cu that allows it to be used in the $\\lambda$-discounted setting, can you discuss a bit more what are the differences between this work and Zhang et al.?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AN1JbEdxA7", "reviewer": "Reviewer_uNa2", "summary": "This paper studies Discounted Online Convex Optimization (OCO) to minimize the λ-discounted regret. The\nauthors introduce a Smoothed OGD (SOGD) algorithm to achieve uniform discounted regret $O(\\sqrt{\\log(T)/(1-\\lambda)})$\nacross a continuous interval of discount factors without prior knowledge of $\\lambda$. They also provide a novel analysis of DNP-cu under discounted payoff settings, showing that it can combine experts operating under different discount factors.", "questions": "1. Can the problem be extended to settings with strongly convex or exp-concave losses? What regret bounds could be achieved?\n\n2. How sensitive is SOGD to the choice of $Z$ and $\\tau$? Are there practical guidelines for setting these parameters in real applications?\n\n3. How does SOGD compare empirically and theoretically with state-of-the-art algorithms with strong adaptive regret when evaluated under discounted regret?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The application of DNP-cu to combine experts with different discount factors is novel and the analysis of DNP-cu under discounted payoffs (Theorem 2) is a key contribution.\n\n2. The paper provides a uniform regret bound across a continuous interval of $\\lambda$ with detailed and well-organized proofs in the appendix.\n\n3. The paper is well-structured with clear motivation, problem setup and technical exposition. The presentation of figures and algorithms help illustrate the main ideas.\n\n4. The authors provide clear statement of problem setting and experimental setup, supporting the reproducibility of both the theoretical and empirical findings.", "weaknesses": "1. The experiments conducted in the paper only compare the performance of SOGD with typical OGD. It would be valuable to compare with other adaptive or meta-learning baselines.\n\n2. Computational Practicality: The theoretical bounds of this paper depend on several constants and assumptions, which may lead to limited practicality and expensive computational cost in high-dimensional or large-scale settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)