Combinatorial Rising Bandits
Authors: Seockbean Song
Youngsik Yoon
Siwei Wang
Wei Chen
Jungseul Ok
Venue: ICLR 2026 Poster (2026)
Keywords: Combinatorial online learning
Rising bandit
Hierarchical planning
Primary area: reinforcement learning

Abstract: Combinatorial online learning is a fundamental task for selecting the optimal action (or super arm) as a combination of base arms in sequential interactions with systems providing stochastic rewards.
It is applicable to diverse domains such as robotics, social advertising, network routing, and recommendation systems.
In many real-world scenarios, we often encounter rising rewards, where playing a base arm not only provides an instantaneous reward but also contributes to the enhancement of future rewards, e.g., robots improving through practice and social influence strengthening in the history of successful recommendations.
Crucially, these enhancements may propagate to multiple super arms that share the same base arms, introducing dependencies beyond the scope of existing bandit models.
To address this gap, we introduce the Combinatorial Rising Bandit (CRB) framework and propose a provably efficient and empirically effective algorithm, Combinatorial Rising Upper Confidence Bound (CRUCB).
We empirically demonstrate the effectiveness of CRUCB in realistic deep reinforcement learning environments and synthetic settings, while our theoretical analysis establishes tight regret bounds. Together, they underscore the practical impact and theoretical rigor of our approach.

Published as a conference paper at ICLR 2026
COMBINATORIAL RISING BANDITS
Seockbean Song", Youngsik Yoon²; Siwei Wang', Wei Chen', Jungseul Ok!
'Graduate School of Artificial Intelligence, POSTECH, Pohang, Korea :Department of Computer Science and Engineering, POSTECH, Pohang, Korea *Microsoft Research Asia, Beijing, China
shinebcbo, jungseul ( @postech. ac.kr
ABSTRACT
Combinatorial online learning is fundamental task for selecting the optimal action (or super arm) as a combination of base arms in sequential interactions with systems providing stochastic rewards. It is applicable to diverse domains such as robotics, social advertising, network routing, and recommendation sys- tems. In many real-world scenarios, we often encounter rising rewards, where playing a base arm not only provides an instantaneous reward but also con- tributes to the enhancement of future rewards, e.g., robots improving through practice and social influence strengthening in the history of successful recommen- dations. Crucially, these enhancements may propagate to multiple super arms that share the same base arms, introducing dependencies beyond the scope of existing bandit models. To address this gap, we introduce the Combinatorial Ris- ing Bandit (CRB) framework and propose provably efficient and empirically effective algorithm, Combinatorial Rising Upper Confidence Bound (CRUCB). We empirically demonstrate the effectiveness of CRUCB in realistic deep rein- forcement learning environments and synthetic settings, while our theoretical analysis establishes tight regret bounds. Together, they underscore the practical impact and theoretical rigor of our approach. Our code is available at https: //githuss www m1 wwoo//mlppsttccc//ee Coob wwweeiinnttiaiiiiiiieii Rising--aannn BBnddits..
INTRODUCTION
Combinatorial online learning studies how to select an optimal action (super arm) composed of multiple sub-actions (base arms). This formulation captures the structure of many practical decision- making problems, including robotics (Xu et al., 2025; Wakayama & Ahmed, 2024), social advertising (Ge al., 2025), automatic machine learning (Huang et al., 2021), network routing (Lagos al., 2025), and recommendation systems (Atalar & Loe-Wony 2025; Zhu & Van Roy, 2023).
However, previous studies of combinatorial online learning have largely neglected the presence of a rising reward nature in practice, where pulling a base arm not only yields an immediate reward but also enhances future rewards. For example, in robotic planning, hierarchical approaches tackle complex tasks by decomposing them into low-level skills, such as grasping and lifting, which act as sub-actions, while the full sequence of these skills constitutes an action. As these low-level skills are reused across different plans, their performance improves (Jansonnie et al., 2024; Mao et al., 2025), reflecting the rising reward nature. Additional real-world scenarios are presented in Appendix
A complementary line of work studies rising bandits, where the expected reward of an arm enhances each time the arm pulled (Fiandri et al., 2024a; Genalti et al., 2024; Heidari et al., 2016; Metelli al., 2022). However, these studies consider only non-combinatorial settings and, therefore, ignore the structural dependencies that arise when different super arms share base arms. Such overlap couples reward dynamics and makes the problem substantially more complex: while repeatedly pulling a single arm is optimal the non-combinatorial setting (Heidari et al., 2016), characterizing optimal policy in the combinatorial regime is far more intricate. A detailed comparison with existing rising bandit formulations is provided in Appendix B.
"Equal contribution CCoresponning author; Jungseul Ok < -jjungseul@postechh.oo

---

Published as a conference paper at ICLR 2026
x10*
X10
1.0-
CRUCB (Ours)
number of pulls
shareed edge
outcome
0.8
SW-CUCB
R-edi
CRUCO 10unt CUCE
0.6
Ried UCD
reg
0.4
edge
2-
cartyy
0.2
early peaker
1-
penker
late
late bloomer
aloomer
0
10K
20K
30K
0
250K
500K
0
250K
500K
number of pulls
episode number
episode number
(a) Toy graph
(b) Outcome functions
(c) Cumulative regret
(d) Empirical number of pulls
Figure 1: Toy example for online shortest path planning. (a) Graph: two paths from to g. early peaker path (( ((shared edge, early peaker)) and a late-bloomer path ([shared edge, late bloomer)). (b) Outcome functions: shared edge rises slowly; early peaker starts high but flattens; late bloomer starts low but rises quickly, eventually surpassing the early peaker, so the late bloomer path is optimal for long horizon T', The reward is the sum of the outcomes of the base arms. (c) Cumulative regret under three algorithms: CRUCB (ours); SW-CUCB (Chen et al., 2021) (combinatorial bandits); R- ed- ACC (Metelli et al., 2022) (rested rising bandits). CRUCB becomes nearly flat, while SW-CUCB and R-ed- ACBU accumulate linear regret. (d) Empirical number of pulls of each edge: CRUCB pulls entirely the late bloomer, SW-CUCB the early peaker, and R-ed-UCB splits pulls roughly evenly.
To model such scenarios, we propose the Combinatorial Rising Bandit (CRB) framework. In this framework, (i) the policy selects super arm (a set of base arms), and (ii) the outcome of each base arm follows a (rested) rising nature such that the expected outcome of a base arm increases after pulling it as part of the selected super arm. We emphasize that CRB addresses unique problem that combinatorial bandits (Chen et al., 2013) and rising bandits (Heidari et al., 2016; Metelli et al., 2022) cannot address. While individual base arms behave like rising bandits, super arms do not: shared base arms create dependencies across super arms, leading to partially shared enhancement. Figure shows an illustrative example. As depicted in Figure 1d, our proposed algorithm, CRUCB, rapidly converges to selecting the late bloomer path, whereas SW-CUCB (Chen et al., 2021). a combinatorial bandit algorithm, consistently selects the early peaker path due its inability account for the rising nature. R-ed-UCB (Metelli et al., 2022), a rising bandit algorithm that ignores the combinatorial structure. splits pulls between both paths because it incorrectly interprets cumulative increments from repeatedly pulling the shared arm as immediate growth, causing it to hallucinate ongoing potential in the early peaker path. This partially shared enhancement distinguishes CRB from prior formulations, introducing fundamentally new challenges. Indeed, this difference also leads to different characterization of optimality in CRB.
To address the challenges introduced by the partially shared enhancement in CRB, we propose Combinatorial Rising UCB (CRUCB), a provably efficient algorithm. CRUCB employs a Future- UCB index that optimistically estimates the future outcome of each base arm by combining its recent mean, slope, and uncertainty term, and then solves a combinatorial optimization problem using these estimates of future rewards to select the super arm. On the theoretical side, derive regret upper bound for CRUCB and a regret lower bound for CRB, and show that these bounds are close, demonstrating the near-optimal efficiency of our approach. On the empirical side, conduct extensive experiments comparing CRUCB with a set of baselines in both synthetic environments and deep reinforcement learning tasks, training neural agent for navigation. These results consistently highlight the superiority of CRUCB and its ability to handle challenges that existing approaches cannot. Therefore, our study positions CRUCB at the intersection of theory and practice: it not only provides provable guarantees but also exposes the limitations of prior methods in realistic environments and demonstrates how CRUCB effectively overcomes them.
Our main contributions are summarized as follows:
We introduce the Combinatorial Rising Bandit (CRB) framework Section 2 to formalize rising reward dynamics in combinatorial settings. Furthermore, we analyze the structure of optimal policies, highlighting that CRB differs from prior frameworks and makes the characterization of optimality both intractable and more intricate in Section 3.
We propose Combinatorial Rising UCB (CRUCB), a provably efficient algorithm for CRB in Section 4, and provide a regret upper bound that nearly matches a corresponding regret lower bound, demonstrating its theoretical tightness in canonical settings in Section 5.
2

---

Published as a conference paper at ICLR 2026
We extensively validate CRUCB in both synthetic and deep reinforcement learning environments Section 6. confirms that CRUCB effectively overcomes the difficulties of the combinatorial rising structure left unsolved by prior methods, while maintaining robustness in practical settings beyond theoretical assumptions.
PROBLEM FORMULATION
We study the Combinatorial Rising Bandit (CRB) problem, where the mean outcome of each base arm increases with the number of plays. Let K be the number of base arms, [K] == {1..... K}. and S C 2| the set of valid super arms. At each round 6, super arm S, E S is chosen, and each i E S, yields an outcome (1) drawn independently from a distribution Di(Nut,i)> where N₁,,-1
number of past plays of arm up to We assume that (,(n) is odssubauusiin with known a, and define μ4: (n) (x=D.(m) (X), where (n) [0, for all i, n. The rising condition requires:
(n()) = pi(n + 1) (n) 2 0, Vi E [K] 21
(1)
Given a chosen super arm S. and the outcome vector X, = (x,(t) E S.}. the reward is R2 : R(S,, Xt), where R is fixed function. We consider canonical setting of semi-bandit feedback at time i.e., π selects super arm S, based on history Ft-1 = {(Sy, xx) I'' E [[--
For analytical tractability, assume the concavity of μss in Heidari et al. (2016):
Assumption 1. (Concavity of (4)) For each [K] and n 2 1, we have (n) 2 (n + 1).
We further assume the monotonicity of the reward function, which is canonical in combinatorial bandit literature (Chen et al., 2016; Wang & Chen, 2018; Wang et al.. 2023):
Assumption 2 (Monotone reward). For each super arm S, the expected reward can be expressed as function of the mean outcomes of its base arms. Formally, there exists a function such that
E [ X)] r(S, 14); / =14 (
(2)
where X denotes the outcome vector. Moreover, is monotone: for any S. S and vectors μ., μr' with 14; S n4 for all i E S, we have r(S, μ1) I w'). Additionally, we assume r(S, 0) = 0.
We note that this assumption verified by various choices of reward functions such as the additive function (Combes et al., 2015; Kveton et al., 2015) and k-MAX function (Wang et al., 2023).
Regret minimization For policy n. its expected cumulative reward over horizon T is E, Exerry R. Let x² arg max, E, Exem Rg
be the optimal policy. Then the regret
of π is defined as:
Reg(n, T) E,,
Σ AE(T]
R
E
Σ R LEIT
where we want to design 7 minimizing this.
CHARACTERIZATION OF OPTIMALITY
We first study the structure of the optimal policy for CRB. Our key finding is that although the optimal policy is complex in general, constant policy, which constantly plays the same super arm, can often serve as an effective and even optimal strategy under mild assumptions. We begin with a formal definition of optimal constant policy, which is the best among all possible constant policies.
Definition (Optimal constant policy). For any super arm S E S, let S denote the constant policy that selects S at every round, i.c., n: (t) S, for each t E [T'. The optimal constant policy is S count, where Sx Souss arg max Ex, Eietry Rt).
Toonst
We note that t is optimal in non-combinatorial rising settings (Heidari et al., 2016). which special instances of CRB such that S = ({1), (2)..., (.... {K}}. However, we found that in general, const is not (exactly) optimal:
3

---

Published as a conference paper at ICLR 2026
Theorem 1. Under Assumptions I and 2, there exists instance of CRB in which Teonst is not optimal.
The proof is provided in Appendix C.I. As shown in the proof, the optimal policy may begin with combination of early peakers and late bloomers (as introduced in Figure 1), before eventually selecting a pure combination of late bloomers to maximize long-term rewards. This implies the optimal policy can be more complex than constant policies due to the partially shared enhancement.
As such, sone is not exactly optimal CRB. However, can still serve as a good approximation under mild assumptions. In particular, if the reward function satisfies additive-bounde reward assumption, which encompasses important reward functions such as additive and k-MAX rewards, cansst achieves cumulative reward close to that of the overall optimal policy.
Theorem 2. Assume that the reward function is bounded above and below by an additive function for each super arm S E S and any μ [0, 1]
Br Σ 14 S r(S, S BU Σ Pi. iES
iES
where B5 and By are non-negative constants.
Then, under Assumptions 1 and 2, the cumulative reward ratio of the optimal constant policy Tomns to the optimal policy x² is bounded as
F EiE(T) Re
Bu
I
(5)
B Ererty Rs.
B1
We can interpret the ratio By a degree of how far the reward function deviates from the additivity.
Bs. Then, Theorem implies that the optimal constant policy can be optimal when the reward function effectively additive. Indeed, when the reward function is additive, i.e., By Br, the exact optimality of optimal constant policy Tonst guaranteed:
Corollary 1. Given additive reward r, Fooor is exactly optimal.
The proof of Theorem 2 is provided in Appendix C.2.
4 PROPOSED METHOD: CRUCB
We propose the Combinatorial Rising UCB (CRUCB) algorithm, presented in Algorithm 1. At each round, CRUCB proceeds two stages: (i) estimates the potential of each base arm using Future-UCB index based on the recent average outcome, the estimated rate of improvement and an exploration bonus, and then (ii) it calls Solver to select the best super arm after solving a combinatorial optimization problem over the estimated indices.
Algorithm 1 Cww.iootoooiiio
Rising UCB (CRUCB)
Input No. + 0 for all E [K], Sliding window parameter E. Initialize Play an arbitrary super arm including base arm twice for each E [K].
for E (2K + 1,..., T)) do
Calculate Future-UCB (+(()) for each base arm, where f1+(t) is defined in equation 6. S. - Solver (Í4 (t), (t)(t)... ... fix (t)).
Play S, and observe reward R.
Update F, and Nrt-
end for
4

---

Published as a conference paper at ICLR 2026
Estimation At each time t, for each base arm i, the Future- UCB index (t) is estimated as follows to predict the potential of base arm i:
Ni.1 Σ
(ttt)
1
x,O++
Σ
(t-1) X1(1 -1,0-xx(1110 x4)
hi
h
hg
1= NE,1 h,+1
No,
h1+1
average
(ii) predicted upper bound of d'ippovement
+ a (t- CNo--Ni-1-H +
10 log 8
(6)
(iii) exploration bonus
where a is the standard deviation and h; is the size of the sliding window governing a bias-variance trade-off between employing few recent observations (less biased), compared to many past observa- tions (less variance). Specifically, we define the window size adaptively as h; eN making it grow proportionally with the number of pulls. This design crucial for balancing initial agility with long-term statistical stability. The hyperparameter tunes this bias- varianee trade-off: a smaller uses shorter, more recent history, resulting in a less biased but higher-variance estimate that is more agile in detecting changes. Conversely, a larger averages over longer history, providing more stable, lower-variance estimate that is slower to adapt to the rising reward dynamics.
The index (a(()) consists of three parts:
(i) recent average: It is the mean of most recent hG outcomes from playing base arm i, and indicates the expected immediate outcome of playing base arm i.
iii predicted upper bound of improvement x.(U)-X.(l-A,, is the estimated slope by finite by difference method. Then, by linear extrapolation, (t-1) x((0)-X((-kaa)) is an estimate of improvement in the average outcome when playing for (L-N...1) times. By the concavity Assumption I, the expectation this term is always optimistic compared to the true value.
(iii) exploration bonus: accounts for uncertainty and encourages exploration of arms that have not been sufficiently often. The exploration bonus used here is intentionally larger than typical bonuses in UCB-based algorithms for stationary bandit settings (Auer al., 2002), because CRUCB predicts future rewards in rising setting, where uncertainty is inherently greater.
Solver After estimating the potential of each base arm, CRUCB employs Solver, which solves a combinatorial optimization problem. Solver takes the estimated Future-UCB indices of the base arms j = ( (4).- ... px (1) as input and selects the super arm with the highest expected reward, i.e., Solver = arg m r(S, p)). This use of a problem-specific optimization oracle is a standard convention in the combinatorial bandit literature (Chen et al. (2013)). The Solver is an interchangeable component, and its implementation depends on the specific combinatorial structure of the task. For example, in the online shortest path problem, Solver ver can be instantiated as Dijkstra's 's algorithm (Dijkstra, 1959).
REGRET ANALYSIS
5.1 REGRET UPPER BOUND CRUCB
We establish an upper bound on the regret of CRUCB and analyze how it adapts to different levels of problem difficulty. To characterize the difficulty CRB instance, we introduce a cumulative increment T(M, 9) := EiEMM-I) max (1))) (Metelli et al., 2022). Intuitively, T(M, q) quantifies the difficulty of CRB instance by measuring the overall outcome growth in expected outcomes. Using ( q), we establish a regret upper bound for CRUCB as follows:
Theorem 3. Assume that the reward function satisfies Lipschitz assumption
Ir(S, (
Σ iES
1 14=1411
5

---

Published as a conference paper at ICLR 2026
where B is Lipschitz constant. Let Te be CRUCB with h, EN Under Assumptions 1 1&2, for
T > 0. q E [0,1]. and & (0, 22). we have the following regret upper bound:
Reg Ne, 5) 2+
Lu²
K+
BKT
T (1-2:)
LT
+
3K
(2BoT) (6llg 4T)
(8)
3
1-
K
(f)
(36)
where L == maxses [S] is the maximum size of a super arm.
Term (i) captures the regret caused by the inherent difficulty of the CRB problem, which related to the rising nature of expected outcomes and the size of super arm. First, when outcomes of base arms evolve continuously, i.e., Y is large, identifying the optimal super arm becomes significantly more difficult, since early observations may not reflect the long-term value of each base arm, making it harder to distinguish the optimal super arm without extensive exploration. Second, when the maximum super size J. is large, the complexity of accurately estimating the combined reward increases, making it harder to confidently identify the optimal super arm. These challenges are quantified by term (i) via the cumulative increment Y and L, which scales as O(KTY LT : q)). Term (ii) captures the regret due randomness in observed outcomes and scales as O(KT2/3(0og T)3/))
It is important note that q is not hyperparameter of the algorithm but purely analytical tool used in our proof. The algorithm's implementation is completely independent of q. Its sole purpose in analysis is to provide single, unified regret bound that holds across wide spectrum of reward- growth patterns by summarizing the cumulative effect of rising rewards. Thus, our theorem guarantees CRUCB's performance uniformly, while the algorithm itself operates without any knowledge of q. The proof of Theorem is provided in Appendix C.3.
The dominant term in the regret bound depends the difficulty of the instance. When T is large, corresponding to more difficult instances, term (i) becomes dominant, potentially leading to linear regret (T)) To characterize the effect of problem difficulty on the regret bound, we present the following corollary, which refines the analysis by assuming an explicit upper bound on the slope %.
Corollary 2. For a non-increasing function f. assume (n) S ('n) for each E [K] and n 2 For T 2 0, q E 10, and 5 E (0, 1/2), the regret of CRUCB Te is bounded as follows:
for
(1-2z) 4T
f(n)9dn) )
Reg(#e: - max KT3 (log $) KT
(9)
In particular, we instantiate the regret upper bound with of with various learning difficulties:
If fn) cxp( -n). If fn) (n+ + 1 and 1, Reg( T" O(T).
Reg(Te, T) O log KT$)
(10)
(11)
Reg( T') O (max (I'S log KT T log 4))
If f()) = (n + 1) and
(12)
To make the role of problem difficulty more explicit, Corollary reformulates the regret bound in terms of (n). This allows the cumulative increment to be explicitly bounded in terms of f(n).
enabling an analytical characterization of the regret.
The regret bounds given in Corollary 2 reflect how the difficulty of the CRB instance varies with the choice of f(n), as illus- trated in Figure 2. When f(n) exp(-n), outcomes saturated rapidly, making it feasible to disregard the rising nature and re- sulting in sub-linear regret. In contrast, when f(n) (n mn+11 1) with E 1, outcomes change gradually, necessitating sustained exploration, and consequently resulting in linear regret. An in- teresting intermediate regime appears when f(() (n + 1) with с > 1, where the regret upper bound explicitly depends on the problem difficulty (parameter c), highlighting adaptivity of CRUCB. This adaptivity will become clearer through the regret lower bound analysis in next section with Figure 3.
1.0
fin) = expi-n)
fin (n +1/
0.0
50
100
Figure 2: Growth of outcomes.
pt induced by (x(n=CC(( with C' as a normalizing constant.

---

Published as a conference paper at ICLR 2026
5.2 REGRET LOWER BOUND OF CRB
In this section, we establish regret lower bounds for CRB. Our results highlight two key findings. First, without any additional assumptions, the regret lower bound is Q(T), reflecting the intrinsic difficulty of CRB. Second, given restricted outcome growth, the regret lower bound can be sub-linear. To analyze the regret across class of CRB instances, we make the dependence on the instance explicit and write the regret as Reg (T, T') in this section.
We begin with general class of CRB without any structural assumptions on the slope 7/-- Theorem 4. (Regret lower bound over general class) Fix sufficiently large time T. Let I be the set of all available CRB instances. Then, any policy π suffers regret:
min max Reg, (F, T) ( WET
(ILT))
(13)
where L is the maximum size of super arms.
Theorem establishes that, without any structural assumptions, no algorithm can achieve sub-linear regret. However, seen in the regret upper bound analysis of CRUCB (Corollary 2), not all instances necessarily incur linear regret. This discrepancy motivates finer analysis: by considering a more fine-grained instance class, we can distinguish between instances that are inherently difficult and those that allow efficient learning, which the regret lower bound becomes sub-linear. The proof of Theorem is provided Appendix C.4.
Theorem 5. (Regret lower bound over a fine-grained class) Fix sufficiently large T. For arbitrary constant 1 < c < 2, define fine-grained set of CRB instances Ao as follows:
Ae = 74(1) S (n++)) , (EIKK], 11]}
(14)
Then, for any policy π incurs regret: minmax Reg. = mmax LVT, MEAc
LT2-
(15)
where L == maxses |S] is the maximum size of super arm.
Theorem 5 characterizes how the regret lower bound varies with parameter c. As also reflected the upper bound, serves as a structural separator between easy and difficult instances: a larger leads to slower outcome growth and a smaller regret lower bound, while smaller result in faster growth and higher regret lower bound. The proof of Theorem 5 is provided in Appendix C.5.
Upper bound (Cor. 2)
Lower bound (Thm. 465)
Order of regret bound
2/3
1/2
As final remark for Section 5, our CRUCB achieves regret upper bound that closely matches the regret lower bound of the CRB (see Figure 3). In particular, without requiring any prior knowledge about the difficulty of the problem instance (e.g., the outcome growth parameter c), CRUCB effectively adapts to varying problem difficulties, ensuring robustness of CRUCB across diverse scenarios. To the best of our knowledge, this represents the first explicit and rigorous comparison between regret upper and lower bounds in the rising bandit literature, highlighting key theoretical contribution of our work.
3/2
Figure 3: Regret bound gap. The regret lower bound of CRB and the regret upper bound of CRUCB when f(m) 1)-- For 1, both the upper and lower bounds are equal to 1. Specifically, for <<<<I 1.5, the lower bound (2-c) and the upper bound (2) are of sim- ilar order, indicating that the regret bounds closely match.
EXPERIMENTS
We evaluate the performance of CRUCB against existing state-of-the-ard algorithms for rising and non-stationary bandits on the online shortest path planning, in both synthetic environments (Sec- tion 6) and realistic deep reinforcement learning applications (Section 6.2). Unlike prior works that mainly focus on simplified rising bandit settings, our evaluation further considers realistic deep RL scenarios, underscoring the practical relevance and robustness of CRUCB. Additional results on diverse combinatorial tasks, including maximum weighted matching, minimum spanning tree, and the k-MAX problem are provided in Appendix F.
7

---

Published as a conference paper at ICLR 2026
1.0
1.0
outcome
0.6
0.6
0.4
0.4
0.2
0.2
late bloomer
late bloomer
10K 50K
10K
number pulls
number of pulls
(a) Path-easy graph
(b) Outcome functions (c) Path-complex graph
(d) Outcome functions
Figure Online shortest path planning task. (a, c) Graphs used evaluate CRUCB and baselines.
(b, d) Corresponding outcome functions for each task.
X10*
x100
CRUCB (Ours)
R-ed-UCB
regret
regret
SW-CUCB
SW-UCB
2
SW-CTS
SW-TS
0
100K
200K
300K
0
250K episode number
500K
episode number
Path-casy
(b) Path-complex
Figure 5: Cumulative regret in synthetic environments. Regret curves for (a) Path-easy and (b)
Path-complex. Lines show average; shaded areas indicate 99% confidence intervals over 5 runs.
Baselines
We consider the following baseline algorithms:
R-ed-UCB (Metelli al., 2022) non-combinatorial algorithm for rising bandits, combining sliding window with
estimation designed for rising rewards.
SW-UCB (Garivier Moulines, 2011) and SW-TS (Trovo et al., 2020) are non-stationary non-combinatorial bandit algorithms that use diding-windood approach with UCB and Thomp- son Sampling, respectively.
SW-CUCB (Chen et al., 2021) and SW-CTS are non-stationary combinatorial bandit algo- window approach with UCB and Thompson Sampling, respectively.
rithms that sliding-window
Detailed pseudocode and descriptions of the baselines are provided in Appendix D. For CRUCB, we set the window size parameter 0.125 in our main experiments. We found this to be robust choice, and detailed sensitivity analysis on the impact of is provided in Appendix F.4.
6.1 SYNTIETIC ENVIRONMENTS
We conduct experiments on the online shortest path task using the graph structures shown in Figures 4a and c, each containing two types of edges: early peakers and late bloomers, illustrated in Figures 4b and d, respectively. In these experiments, we assume the additive reward setting in which the reward of super
defined as the of the outcomes of constiruent base arms. In this setting, Corollary implies that the optimal policy is a constant policy repeatedly selecting a fixed path (super arm), which in our experiments corresponds a path composed solely of late bloomers.
As shown in Figure 5a, CRUCB demonstrates lower regret compared to all baselines in the Path-easy task. R-ed-UCB underperforms despite the simplicity of the graph structure, due the partially shared enhancement described earlier in Figure 1. In the more complex Path-complex task, CRUCB continues outperform all baselines, with the gap between CRUCB and R-ed-UCB becomes significantly larger, shown in Figure 5b.
This because the effects of the partially shared enhancement are amplified as the overlap of edges (base arms) among paths (super arms) increases. Interestingly, across both environments, non-combinatorial and non-stationary algorithms (SW-UCB, SW-TS) consistently outperform their combinatorial counterparts (SW-CUCB, SW-CTS), with the gap becoming more pronounced in the complex task. This occurs because the increased number of paths promotes broader exploration, al- lowing non-combinatorial algorithms sufficient time to explore late bloomers, whereas combinatorial algorithms tend to focus exploitation on early peakers, thereby restricting the opportumities for late bloomers enhance their full reward potential.
8

---

Published as a conference paper at ICLR 2026
goal
6
start
e
(a) AntMaze-casy
(b) AntMazz-complex
Figure 6: Deep RL environments. An ant robot navigates the shortest path from start to goal via intermediate nodes, encountering three types of edges in (a): impossible (e1), bottleneck (Eg), and wide (#2, 64, 65, c6, 67) edge. (b) Focus on impossible and wide edges in a complex map.
CRUCB (Ours)
*
R-ed-UCB
SW-CUCB
SW-UCB
SW-CTS
SW-TS
x10'
x10*
15.
1.0
impossible edge
0.8
bettlenedk edge
15
outcome
0.6
wide edge
regret
10
regret
10
0.4
5
0.2
0
0
0
0.5K 1.0K 1.5K
1K
2K
1K
2K
3K
number of pulls
episode number
episode number
(a) Observed outcomes
(b) AntMaze-easy
(c) AntMaze-complee
Figure Cumulative regret in deep reinforcement learning environments. (a) Observed outcomes for each edge with respect to the number of pulls. Regret curves for (b) AntMaze-easy and (c)
AntMaze-complex. Lines show average; shaded areas indicate 99% confidence intervals over runs.
6.2 DEEP REINFORCEMENT LEARNING
We conduct experiments the online shortest path problem using hierarchical reinforcement learning in AntMaee environments (Yoon et al., 2024), as illustrated Figure 6. It divides tasks into high-level and low-level policies. The high-level policy makes abstract decisions, such the path from start to goal, while the low-level policy executes these decisions by controlling the specific movements of the robot. In our setup, the high-level policy plays a role similar to the CRB framework by selecting paths as super arms, where each edge corresponds to base arm. As training progresses, the improvements in the low-level policy lead the rising outcomes for the high-level policy. We consider two tasks: AntMaze-easy and AntMazz-comples (Figures 6a and b). In AntMaze-easy. the policy can choose among three paths: an impossible path using edge (e1). a shorteut path (e2, C3 67) that is short but contains a bottleneck edge e3 requiring more episodes to train, and a detour path (E2, e4, Eb, cg, E7) composed solely wide edges but requiring more steps. The key challenge in this task is to recognize the rising outcome of the bottleneck edge and efficiently exploit the shortcut path despite its initial difficulty. In AntMazze-comples the environment has a complex graph structure with extensive paths from start to goal. The large number of paths increases combinatorial complexity, making exploration and identification of the optimal path challenging. Fach task aims at a distinct challenge: AntMaze-easy focuses capturing the rising reward nature, whereas AntMaze-complex emphasizes robustness against growing combinatorial complexity. Detailed descriptions of the environments and reward structures are provided Appendix E.2.
As depicted in Figure 7a, the outcomes exhibit non-concave behavior due to an extended zero-reward period before the first success: however, the outcome growth appears roughly concave once the rewards increase. Despite this violation of the concavity assumption (Assumption 1), Figures 7b and show that CRUCB outperforms the baselines, highlighting its robustness in settings where theoretical assumptions are not strictly satisfied. In AntMaze-easy, CRUCB and R-ed-UCH outperform other baselines, as shown in Figure 7b. Given the simplicity of the environment, which includes only three paths, most algorithms successfully identify the detour path. However, non-stationary bandit algorithms tend to exploit the detour path once found and limit further exploration. contrast, rising bandit algorithms continue explore the bottleneck path, eventually identifying the optimal path and resulting in lower cumulative regret.

---

Published as a conference paper at ICLR 2026
Less tried
More tried
goal
goal
goal
500
500
start
start
start
goal
goal
goal
-- 1-334 3,000
t
start
start
start
(a) SW-CUCB
(b) R-ed-UCB
(c) CRUCB (Ours)
Figure 8: Heatmap of visit frequencies in AntMaze-complex. We visualize the visit frequencies of SW-CUCB, R-ed-UCB, and CRUCB at time steps 500 and 3,000 to highlight their respective exploration patterns. Visualizations of other baselines are provided Appendix G.
As depicted in Figure 8, existing algorithms fail to capture both the combinatorial structure and the rising nature simultaneously. Figure 8a shows thick traces around blocked walls, indicating that the agent repeatedly attempts the same impossible edges. This behavior stems from the agent's ' evaluation, where it perceives a single impossible edge more optimistic path than a detour path composed of multiple low-reward edges. Conversely, R-ed-UCB performs uniform exploration as illustrated in Figure 8b. This broad search is unavoidable consequence of initially treating all 178 possible paths as independent super arms. Even after a sufficient amount of time, its inability to leverage partially shared enhancements leads incorrect estimations, causing the agent continue exploring various paths instead of converging on the optimal path. In contrast, CRUCB, as depicted in Figure 8c, integrates both perspectives: it avoids repeated trials on impossible paths, efficiently exploits shared improvements, and quickly concentrates on the optimal path. These observations confirm that the limitations of existing approaches highlighted in Section arise in practice and demonstrate that CRUCB successfully overcomes them.
7 CONCLUSION
In this work, we introduced the Combinatorial Rising Bandit (CRB) framework, modeling combi- natorial online learning scenarios wherein selecting a super arm enhances the future rewards of its constituent base arms. By highlighting the novel challenges from the purtially shared enhancement in Figure we established that CRB fundamentally differs from classical bandit formulations. To address this challenge, algorithm. Our extensive experiments across synthetic and deep RL environments demonstrate that CRUCB robustly handles the combinatorial rising structure where prior methods fail. At the same time, our theoretical analysis establishes tight regret bounds, showing that the algorithm is nearly optimal from analytical standpoint. Taken together, these results highlight that CRUCB offers both tangible benefits in practice and solid guarantees in theory. While our analysis relies on simplifying assumptions, such fixed set of base arms and static combinatorial structure, these are often reasonable in domains where the action space is pre-defined. However, in certain applications, such as robotic systems that involve skill discovery, the set of feasible actions may evolve over time. Extending CRB to handle such dynamic structures is promising direction for future research.
developed Combinatorial Rising UCB (CRUCB), provably efficient
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported by the Institute for Information & Communications Technology Planning Evaluation (IITP) grant funded by the Korean government (MSIT) NN..RS-2019-11191111 Artifi- cial Intelligence Graduate School Program (POSTECH); No.RS-2024-006 2024-00436680, Global Research Support Program in the Digital Field; N..RS-2024-04557852 AI Research Hub Project); the Korea Institute for Advancement of Technology (KIAT) grant funded by the Ministry of Trade, Industry and Energy (MOTIE)
the Seoul R&BD Program (No.SP240008) through the Seoul Business Agency (SBA) funded by the Seoul Metropolitan Government, This project supported by Microsoft Research Asia.
REFERENCES
Omer Amichay and Yishay Mansour. Rising rested mab with linear drift. arXiv preprint arXiv:2501.04403 2025.
Baran Atalar and Carlee Joe- Wong. Neural combinatorial clustered bandits for recommendation systems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 15417- 15426, 2025.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47:235-2565 2002.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In Proceedings the 30th International Conference on Machine Learning, pp. 151-159. PMLR, 2013.
Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. Combinatorial multi-armed bandit with general reward functions. Advances in Neural Information Processing Systems, 29, 2016.
Wei Chen, Liwei Wang. Haoyu Zhao, and Kai Zheng. Combinatorial semi-bandit in the non- stationt environment. In Uncertainty in Artificial Intelligence, pp. 865-875. PMLR, 2021.
Richard Combes, Mohammad Sadegh Talebi Mazrach Shahi, Alexandre Proutiere, and mare lelarge. Combinatorial bandits revisited. In Advances in Neural Information Processing Systems, volume 28, pp. 2116-2124, 2015.
Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, pp. 269-271, 1959.
Marco Fiandri, Alberto Maria Metelli, and Francesco Trovo. Rising rested bandits: Lower bounds and efficient algorithms. arXiv preprint urXiv:2411. 14446, 2024a.
Marco Fiandri, Alberto Maria Metelli, and Francesco Trovò. Thompson sampling-like like algorithms for stochastic rising rested bandits. In Seventeenth European Workshop on Reinforcement Learning, 2024b.
Aurélien Garivier and Eric Moulines. On upper-contidence bound policies for switching bandit problems. In International conference on algorithmic learning theory, pp. 174-188. Springer, 2011.
Lin Ge, Yang Xu, Jianing Chu, David Cramer, Fuhong Li, Kelly Paulson, and Rui Song. Multi-task combinatorial bandits for budget allocation. Proceedings of the 31st ACM SIGKDD Conference Knowledge Discovery and Data Mining V. I, pp. 2247-2258, 2025.
Gianmarco Genalti, Marco Mussi, Nicola Gatti, Marcello Restelli, Matteo Castiglioni, and Al- berto Maria Metelli. Graph-triggered rising bandits. In Forty-first International Conference on Machine Learning, 2024.
Hoda Heidari, Michael Kearns, and Aaron Roth. Tight policy regret bounds for improving and decaying bandits. In I/CAI, pp. 1562-1570, 2016.
11

---

Published as a conference paper at ICLR 2026
Hanxun Huang, Xingjun Ma, Sarah M Erfani, and James Bailey. Neural architecture search via combinatorial mulli-arreed bandit. In 2021 International Joint Conference on Neural Networks (JJCNN), pp. 1-8. IEEE, 2021.
Paul Jansonnie, Bingbing Wu, Julien Perez, and Jan Peters. Unsupervised skill discovery for robotic manipulation through automatic task generation. In 2024 IEEE-RAS 23rd International Conference on Humanoid Robots (Humanoids), pp. 926-933. IEEE, 2024.
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. In Artificial Intelligence and Statistics, pp. 535-543. PMLR, 2015.
Tomás Lagos, Ramón Auad, and Felipe Lagos. The online shortest path problem: Learning travel times using a multiarmed bandit framework. Transportution Science, 59(1):28-55 2025.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Xiaofeng Mao, Yucheng Xu, Zhaole Sun, Elle Miller, Daniel Layeghi, and Michael Mistry. Learning Long-horizon robot manipulation skills via privileged action. arXiv preprint arXiv:2502.1544. 2025.
Alberto Maria Metelli, Francesco Trovo, Matteo Pirola, and Marcello Restelli. Stochastic rising bandits. In International Conference on Machine Learning, pp. 15421-15457. PMLR, 2022.
Marco Mussi, Alessandro Montenegro, Francesco Trovo, Marcello Restelli, ALBERTO Metelli, et al. Best arm identification for stochastic rising bandits. In Proceedings of the 41st International Conference on Machine Learning, pp. 1-9, 2024.
Vishakha Patil, Vineet Nair, Ganesh Ghalme, and Arindam Khan. Mitigating disparity while maxi- mizing reward: tight anytime guarantee for improving bandits. arXiv preprint arXiv:2208. 09254, 2022.
Francesco Trovo, Stefano Paladino, Marcello Restelli, and Nicola Gatti. Sliding-window thompson sampling for non-stationary settings. Journal of Artificial Intelligence Research, 68:31 1-364, 2020.
Shohei Wakayama and Nisar Ahmed. Observation Enservation-augmented contextual multi-armed bandits for robotic search and exploration. IEFF Robotics and Automation Letters, 2024.
Siwei Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. In International Conference on Machine Learning, pp. 5114-5122. PMLR, 2018
Yiliu Wang, Wei Chen, and Milan Vojnovié. Combinatorial bandits for maximum value reward function under max value-index feedback. arXiv preprint arXiv:2305. 16074, 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models, Advances in neural information processing systems, 25:24724-24837, 2022.
Yu Xia, Fang Kong, Tong Yu, Liya Guo, Ryan A Rossi, Sungchul Kim, and Shuai Li. Which Ilm to play? convergence-aware online model selection with iimeiinceassing bandits. In Proceedings of the ACM on Web Conference 2024, pp. 4059-4070, 2024.
Lily Xu, Bryan Wilder, Elias Boutros Khalil, and Milind Tambe. Reinforcement learning with combi- natorial actions for coupled restless handits. In The Thirteenth International Conference on Learn- ing Representations, 2025. URL https: : wwwpneevieeeeeeeeeeeeeo www.///e/eee..eeee..m....... forum ? 3 LbAA 6F6.
Youngsik Yoon, Gangbok Lee, Sungsoo Ahn, and Jungseul Ok. Breadth-first exploration adaptive grid for reinforcement learning. In Forty-first International Conference on Machine Learning, 2024.
Chuanyang Zheng, Zhengying Liu, Enze Xie, Zhenguo Li, and Li. Progressive-hin prompting improves reasoning in large language models. arXiv preprint arXiv:2304.099 09999797797.. 2023.
Zheqing Zhu and Benjamin Van Roy. Scalable neural contextual bandit for recommender sys- tems. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 3636-3646, 2023.
12

---

Published as a conference paper at ICLR 2026
This material provides proof of theorems, details of environments and baselines, and additional experimental results:
Appendix A: Motivating applications of CRB.
Appendix B: Comparison with existing rising bandit studies.
Appendix C: Proofs of Theorem 1, 2, 3, 4, and 5.
Appendix D: Detailed description and pseudocode of the baselines in Section 6,
Appendix E: Detailed description of the environments Section 6.
Appendix Additional experiments on other combinatorial tasks.
Appendix G: Further analysis of exploration the deep RL environment.
Appendix H: The use of Large Language Models.
13

---

Published as a conference paper at ICLR 2026
A REAL-WORLD APPLICATIONS OF THE CRB FRAMEWORK
The CRB framework, which addresses a regret minimization problem, naturally arises real- world scenarios where complex actions are composed of reusable sub-actions that improve through repetition. We can consider following applications:
Network Routing optimizes performance metrics such latency or throughput by selecting network paths (super arms) composed of individual links (base arms). Frequent utilization of specific links enables routing protocols to adapt and improve via better congestion estimation and traffic- pattern learning. Thus, network routing naturally aligns with regret minimization as it balances exploiting known effective routes and exploring potentially better alternatives.
Crowdsourcing aims to find optimal task assignments by combining annotators (base arms) with datasets, which can be framed as an online combinatorial regret minimization problem (Chen et al., 2016). Annotators' skill levels improve over repeated tasks, increasing their annotation accuracy. CRB effectively addresses regret minimization here by dynamically reallocating tasks among annotators to leverage their rising skills, thereby optimizing overall annotation quality and cost-effeetivveness.
LLM-based Planning decomposes complex tasks into simpler subtasks (base arms), akin to the Chain-of- Thoughh (CoT) approach (Wei et al., 2022). Iterative prompting, where previous outputs refine future ones (Zheng al., 2023), enhances model performance time (rising reward). By applying CRB to decompose tasks into subtasks, we expect improved performance by exploiting the rising reward structure in these iterative reasoning tasks.
14

---

Published as a conference paper at ICLR 2026
B COMPARISON WITH EXISTING RISING BANDIT STUDIES
The rising bandit problem has been widely studied in non-combinatorial settings (Fiandri et al., 2024a;b; Heidari al., 2016; Metelli al., 2022; Mussi et al., 2024; Patil al., 2022; Xia al., 2024; Amichay & Mansour, 2025), where each base arm evolves independently over pulls. In this work, we consider combinatorial extension of the rising bandit problem, where each action is set of base arms. This generalization introduces new challenges that fundamentally differ from previous work.
In previous work (Heidari et al., 2016), it is shown that constant policy is optimal in the rising bandit setting. However in Section 3, we demonstrate that in the combinatorial setting, constant policies are generally not optimal. Furthermore, (Metelli et al., 2022) focus primarily on establishing worst-case regret lower bounds, showing that regret linear (S(T)), highlighting the inherent difficulty of the problem. In contrast, we show that under more fine-grained instance class where reward growth is bounded, the regret lower bound can be sublinear. Moreover, we illustrate that this lower bound is tight, nearly matching with the regret upper bound of our proposed algorithm, CRUCB
recent study (Genalti et al., 2024) investigates rising bandits with structured dependencics among arms, introducing graph-triggered mechanism in which pulling arm increases the rewards of its neighboring arms. While conceptually related to our work, their approach assumes uniform enhancement across neighbors, without modeling the nuanced structure of overlapping actions. In contrast, our CRB framework models partially shared enhancement, preserving the combinatorial structure. This distinction makes CRB more general and unified framework for capturing rising reward dynamics in combinatorial settings.
15

---

Published as a conference paper at ICLR 2026
C PROOF OF THEOREMS
C.1 PROOF OF THEOREM 1
suffices show that there exists a CRB instance such that the constant policy not the optimal policy. We consider k-MAX problem, where reward function is given as follows:
r(S, p) == max
(16)
iES
Note that equation 16 satisfies all assumptions. Consider such that:
10 < T 2
(1(n)
T
10 10
(17)
1
n
0.1
== 1
(2(n)
(18)
0.9
(n( 0.5
(19)
Let K = 3, ((1,)) n-th times, then the outcome is (n) without considering randomness. In this problem instance, the optimal constant policy is selecting the super arm (1, continuously. For the best constant policy, it receives 0.1 for
T > 100. For simplicity, when base arm is pulled for
and 10t T for 1 < t 97 and for t 97' However, if (2,3) is firstly selected once and 21 for the remaining time, receives 0.3 more rewards than the best constant policy.
10
This is because selecting (2,3) initially yields an immediate gain of 0.4 from first selecting, but later results in a loss of 0.1 due to not playing optimal super arm (1,2). Consequently, the total reward is higher than that of the best constant policy, which suffices to complete proof.
C.2 PROOF OF THEOREM 2
For proof, we first consider a specific case: additive reward.
Lemma 1. Given an additive reward r(S. = E'Es Hú, Teomst is exactly optimal.
Set up. Since we consider additive reward function, the eumulative reward is invariant with respect to permutations of the order of selecting super arms, which means that policy can be represented as the vector number pulling each super arm, that is, a policy क can represented as follows:
क - (T T2,
TTs
(20)
where T denotes the number of pulling a super arm S until time T by the policy π, which satisfies Eses Tg = T. Let N denote the number of selecting a base arm i until time T by Then, Nor can be represented as follows:
NOT Sig((ie). SES
(21)
where Il denotes the indicator function. Let x" be the optimal policy given 4 and T'. We show that if n pulls at least two different super arms, then a constant policy can be constructed so that generates larger than or equal the expected cumulative reward the one produced by n², which suffices to conclude.
Assume that ग* selects m distinct super arms, denoted by super arms as S2, S2...., Sm. Define subset of base arms B, and B, for each j E [m] as follows:
B. = (i E [K] i Sj,
[m
(22)
B, = S, B
(23)
B. represents the subset of the common base arms included in every selected super arm by the optimal policy n" and B, represents the subset of base arms included in the super arm S, except for B.
16

---

Published as a conference paper at ICLR 2026
Claim 1. ΣiEB, (N(T)) is equal for all j [m]]
Proof. To establish Claim we consider two arbitrary distinct super arms S1 and S2, with- loss of generality. We observe ΣiEBAA, (N(T)) 2 LiEBAR ((( If not, that is,
EiEB \B BB, (N(()T < EieBarB, M;(NTT)), we can construct new policy follows:
T3 -
S
T
T
+1 S= S2 otherwise.
(24)
T
Then, N is given by:
NIT N No 1,7
1 iE B1 B2
N7
iE B2 B1
(25)
otherwise
The difference between the expected cumulative reward of n- and is given by:
Σ ps(n)
Σ mi(t)
(26)
[E[R]
REINET!
nE(N
Σ
(N(T))
E MG(NTT+ iEBA
(27)
BEB,AB2
<0,
(28)
which indicates that the cumulative reward of is larger than that of n². However, it is contradicting with the assumption that n² is optimal and thus we have Σ BB, (a(NNTT 2
EIEBA,, (N)T)) By applying the same logic, we can also derive that EiEBIBB (i(N S
EIEBAYB, (N Combing these results, have EiEB, M(NN ΣIEBAYB Mi(NT.))
derive that ΣieB, (N(NTT = DiEB, (NNN (,T). Since can apply the same logic to any arbitrary super arm pair, we conclude the claim.
By adding ΣisB, nB, (NN())
Claim 2. EiERAB MN(NTT - Tz. + Eienjrn, (((NTt) for any j. j E [m]]
Proof. Similar to Claim that EiEBiYB, (N(N**)) i.T)
we consider S₁ and S2, without loss of generality. Given ΣiEBYYB, (N(N))) from preceding analysis, we observe
EiEB, \B, Mi(N T +1) EieByeB (:(N))) Otherwise, that is, EiEBA u((N
T3. +1 < Eiengyn, (N(T)) we can construct new policy T2 such that:
0
S = Si
1
T3 + TH
TT
S= S2 otherwise.
(29)
Then, N is given by:
NET Tg. NET T7, NET
iE B1 \ B i Bz B otherwise
NT
(30)
17

---

Published as a conference paper at ICLR 2026
The difference between the cumulative rewards of x² and iy is given by:
Σ
Σ
p=(n)
Σ
mi(n)
(31)
=[[K]
nei
N
Σ
Σ
pa(n) Σ
Σ 14(m)
(32)
iE BEB1'S B3 n= -T
iE Bi n=N
Σ
Σ
MN - T5. +1)
E
Pa(NTT +1)
(33)
[E[T3]]
iEBi\BB
iEBa\Br
Σ
(i
73 +1)
Σ
(i(NT.))
(34)
B
(TT)
Σ iEBi\Ba
(((NTT)
E iEBAB
(((NTTT)
<0,
(35)
where equation 34 holds since (N +1) (N and (N + (NN for
any [2, Tg, for any base arm i by the definition of combinatorial rising bandir. It indicates that the cumulative reward of π2 is larger than that of n², which is contradiction with assumption that π² is optimal. Therefore, we have ΣiEB, \B, MNNN,, T5. + 1) 2 EiEBAAB (N) Combining this observation with the previous observation, we have ELEBI M4 +1)
ΣieB, \ (N(T)) This result implies that rewards of all base arms in S1 are flat after pulling for N - -T3, times. Since we can apply the same logic to any arbitrary super arm pair, we conclude the claim.
Induction. Lastly, we construct constant policy inductively. As before, we choose two arbitrary two super arm and consider S₁ and S₂ without loss of generality. we revisit TT. By Claim I and Claim 2 the difference between x' and equals O, which means that æ2 is also an optimal policy. We remark that T2 plays m distinct super arms. Applying preceding logic inductively, we can construct the optimal policy pulls only one super arm, which completes proof for Lemma 1.
Then, we are ready to prove Theorem 2.
Proof. For the proof, define Sonstt and woustt follows:
S'nn == arg max
Σ
M1stt -1) 1),
(36)
1E[T]
LES
St = arg max
Σ
r(S, us(l 1))
(37)
LE[T]
π Fooss (t) S Sonet
Vt E [T]
(38)
π Touse
(1) = S Stonet
VI E [T),
(39)
where (t - 1) == {er(t- - 1) : E S}. Intuitively, Tioms indicates the optimal constant policy when the reward function is additive and mumas indicates the optimal constant policy when the reward function is given r(-).
18

---

Published as a conference paper at ICLR 2026
Let nT be optimal policy, and denote the selected super arm and expectation of base arm time t under πt" as St and fi respectively. Then, we have:
Ex
Σ LE[T]
R
Σ LE(T]
r(S7 1i-1)
(40)
Σ
((SS, ( r(5),)
(41)
NE(T]
- Bu
1 -)
(42)
rE[T]
sE9;
s Bu
Σ
pi(t (u(t-1) 1)
(43)
[E[T] SE
From Lemma I, we know that the reward under the optimal policy is bounded by the reward under constant arm selection, which leads to the inequality in equation 43.
Now, consider the reward of const Then, we have:
B ST
Σ
R
Σ
r(S
S (1. 1))
(44)
[E
(E(T]
Σ
(r(S) f Souse (t (t-1)) 1)) r(S comstr 0) + r(S 0))
(45)
LE[T]
B,
Σ TE(T)
Σ
(46)
iES
From the inequalities equation 43 and equation 46, we can derive the following ratio:
Em Ene(T Rs
Bu E1E(T) Eiest pb(t 1)
(47)
E B EvE(T] Rs
By EiEm Eie Pt 1)
Bu
(48)
B1
Since Simma is defined maximize the reward have the inequality:
E crent
Σ
R
Σ R
(49)
BE|T
EE(T)
Finally, combining all the inequalities, we conclude:
Ex-
Eve(Ty
Rd
Ex
EiE(T] Ri.
By
(50)
IF Er
Exerrry
R
Enigen
EtEnr
Ri.
B1
19

---

Published as a conference paper at ICLR 2026
C.3 PROOF OF THEOREM 3
Proof. We rewrite the regret as follows.
Reg( T) = Σ
E Re - Σ
EN [Rs]
(51)
LE|T]
LE/21
Σ
r(St 1 )
Σ
E [r(S] Us;))
(52)
SE[T]
Σ
En
(((TT (sp r(tt us
(53)
(E[T]
where equation 52 holds since in semi-bandit feedback setting, the optimal policy is characterized as a deterministic policy.
To define well-estimated event, we define (1) and (1) as follows:
N
Xz(1) + (t - Xz(1) x.(1 - hs)) (ss)
(x(t)= = his N -1+t
Σ
(54)
(a(()= = 1 Ni
(i(1) + (1 - pall)
pa(1 hi)
(55)
hi (=N,,-1 -hit1
h4
10 10 t h
B((t) a (t- -N- + - 1)
(56)
(tt = (t()) + (,(().
(57)
We define well-estimated event &, follows:
& {lix(1) - (x) (,(1))
(58)
& = EiE
(59)
We decompose the regret with well-estimated event & as follows:
Ex r(ST" (ST"") ) r(S, :1ss )
(60)
Ex [r(ST (Spr) - r(St (s57) {{-),} +Ex (F(ST" , ) - r(S7 vs5t)
1(88)
(B)
(61)
Firstly, we bound term (A):
Ex [r((7' -Mss-) r(S7 mss))) 1 1(-),)
L Σ
E, (-(-))
(62)
AE[T]
T, P(-&)
(63)
EE(T]
2LK
Σ
(64)
12
(E(T]
LKT
(65)
3
where equation 64 holds by Lemma 2 and equation 65 holds since 2
77
32
6.
Lemma 2. (Metelli et al., 2022) For every round K < < T, and window size S h, S EN we have:
2K
P(-E) <
(66)
2
20

---

Published as a conference paper at ICLR 2026
Next, we bound term (B). Firstly, we utilize Lipschitz continuity.
r(S (s;-)) ) r(5, (.s))
(67)
-r(s (Ms;7)) ) r(ST (45;) + r r(T (5 (155) -r(ST ,ss)
) + r((t -1sg))))(( (...')
(68)
S r(S, us;)) + r((T, ((5p)) - r(S, (27)) + r(() .Ps.-)
(69)
Sr(S p - -r(S,, (ST))
(70)
<B Σ (k:(t) (x(t)l
(71)
iEST
< Σ (1(1) - (4(1)++++))))))+) 2B Σ 3,(1),
(72)
REST
&EST
(B1)
(B2)
where equation 69 holds by Assumption and equation 70 holds by definition of CRUCB and equation 71 holds by Lipschitz assumption and equation 72 holds by well-estimated event &
We bound the term (B1) defining li,n as the time step where the base arm i pulled the nh time:
Nut
ΣΣ
7=(()) (l) S 2K + Σ
Σ
min (Te(Le,)) (c()),
(73)
(E(T] iEST
iE[K]
Ni.
$ 2K + Σ
min
(2ti. 12 2m + hs - 1)7ann (ac.nnn200 -2,; + +1,1 2
(74)
iE[K] m=3
Nrr
= =2 + Σ Σ
min (T>(((1 - -22)m), 1)
(75)
(E[K] m=3
< 2K + T Σ
Σ
7e((1 2E)n)²
(76)
(E(K)
1 (1-
LT K k.9)
- 2K + KT
r (1 22)
(77)
26
where equation 74 follows from the Lemma A.3, in (Metelli et al., 2022), equation 76 follows from the fact min(s, 1) & min(s, 1)9 < s" for q E [0, 1). and equation 77 follows from the Lemma C.2. in (Metelli et al., 2022). Now, we bound the term (B2).
2 log 413
Σ Σ (E[T] 1EST
2B min (8.(),1} vE[T]iES:
Σ
Σ
2B min
o (1 No.-1 + h4 1) V
:1] (78)
1
Glog 4T [Nee)
Σ
Σ
2B min
To
(79)
(e
LEST iEST
6 6log 47 (=|n 1
Σ
Σ
2B min
To
(80)
K [.(N.
Choose n' ( (6lg(4)))
Then for n'
6 6log 47
2BoT
(E|m])² $1
(81)
21

---

Published as a conference paper at ICLR 2026
Thus, have:
N.
6log 47
6log 47 (=(n))²
Σ k n=1
2B min
oT,
Σ sE[K]
n' +
Σ 2BoT
(82)
V (#(n))a
n=n'+1
6log 47
[o x dx
I K
n' 2BoT
(83)
3K
((2 (6 (
(84)
where equation 83 comes from the fact that the sum of monotone decreasing function can be upper bounded. Combining the results from equation 65, equation 77, and equation 84, we conclude the proof.
C.4 PROOF OF THEOREM 4
Proof. Firstly, we consider non-cone combinaaaaaoia case, which means that every super arm has only one base arm. We construct two different problems and show that no policy can achieve sub-linear regret.
Lemma 3. Let T' be the set of all available two-armed rising bandit problem. For sufficiently large time T, any policy a suffers regret:
min max Reg (T, T) 2 MET'
(85)
16
Proof. For simplicity, we consider the deterministic problem, that is, a 0. Let Rew, (T,, T) be the cumulative reward of policy up to time T with respect to the problem instance Define two problem μ and μ B as follows:
11 (n( = pi (n) =
2
if 2T
12 (n)
1
otherwise
3m
if S fo4 otherwise
12
(n)
H1
12
T
3
3
T
2T 3
T
3
In this setting, define S as follows:
S S= (5,,
(86)
The main idea of the proof is that for any arbitrary policy n', the policy receives the same rewards for both A and 1 at least until &. indicating that:
T
T
Rew
(x:3) 3
Rew n'
(87)
22

---

Published as a conference paper at ICLR 2026
Fix some arbitrary policy and define M follows:
M == F (Ns, 5] = Fu (N
(88)
We compute the cumulative regret of policy in µ and μ²
Problem (A) For n the optimal policy va selects S₂ for every time. The corresponding cumula- tive reward is given by:
22
3n
T
Rew F (T 7)
=
(89)
2T
3
n=
For the given policy the cumulative reward is upper bounded as follows:
T- Main (Ns,r]
Rew na (T, T)
=
[Ns +
u2 (n)
(90)
2
n=1
T M
M
+
H2 (n)
(91)
2
n=1
M
3n
T
+
+
M
(92)
2
27
3
[3]
3n
T
M
(93)
2T
2
where equation 91 holds since the cumulative reward is maximized as E (...r) minimized and M.
is guaranteed that E, [Ns.r]] 2 E,s, [NV [
The cumulative regret lower bounded by:
27
3n
T
3n
T
M
Reg (TT
2
(94)
2T
2T
2
n=1
M
(95)
2
Problem (B) For f the optimal policy Ti is selecting S1, for every time. The corresponding cumulative reward is given by:
T
Rew " n (T T)
(96)
For the given policy the cumulative reward is upper bounded as follows:
T T- Buggrrlee [Ns..rl
1
Rew n (T,, T)
[Nsi.T
+
12 (n)
(97)
2
M)
Σ
12 (n)
(98)
2
n=l
I
Σ
3n
T
M
(99)
27
3
2
==1
3
T
(T
T
M
M
M
+
+
+
(100)
4T
3
3
3
2
3M
3M
57"
+
(101)
47
47
12
4
23

---

Published as a conference paper at ICLR 2026
where equation 91 holds since the cumulative reward is maximized Bun (Ns..2) maximized and it is guaranteed that [-Ns.rr I o/f +
27
3
+ M.
The cumulative regret lower bounded by:
T
3M
3M
5T
!
Reg B (T, (T,T)
(102)
2
47
47
12
3M
3M
T
1
(103)
47
4T
12
4
3M
3M
(104)
47
4T
16
where equation 104 holds since we assume sufficiently large T.
From previous results, the worst-case regret can be lower bounded as follows:
inf sup Reg y (TT, 7) 2 inf max {Reg (TT, T), Reg (T,, T)}
(105)
M
3M²
3M
T
inf max ME [)
(106)
4T
4T
16
-12M² (8T
12) M +
inf Me [
(107)
167
T
(108)
16
where equation 107 holds since max(q a, b) 2 a+b and equation 108 holds since it is easily verified that equation 107 is minimized when M 0, which completes the proof.
Now, expand Lemma 3 to general combinatorial setting, Let L be arbitrary constant. We define two problem f A,L and μ B.I. construct super arm set S,, as follows:
A.L (n) 14
14
B.L (n)
1
iE []
(109)
2
3n 2T
if <
2T 3
14 (n)
(n)
iE 11+1112
(110)
otherwise
if S T otherwise
B. (n) (n) 1i
2T
E [L - 1,2
(111)
Sr. = ((ai, 02 .2,....,1)) a, E (i, L+ iE [4]
(112)
Since it can be interpreted as solving L independent problems, we have:
LT
inf sup Regu (5, T)
(113)
16
C.5 PROOF OF THEOREM 5
Proof. We apply similar logic given in the Appendix C.4 to show that for the worst-case lower bound Ω max LVT, -L .Frssly Firstly, we consider non-combinatorial case.
Let Ale be the subset of two-armed rising bandit problem with constraints given in equation 14, For sufficiently large time T, any policy π suffers regret:
Lemma
min max Reg, (T, T) 2 2 W.A.
(114)
24

---

Published as a conference paper at ICLR 2026
Proof. For convention, we define ju() and F(m) as follows:
m(m)= = Σ
(n + 1
(115)
==1
m
F(m) = Σ p(n).
(116)
Let 4 and 4 3 be two rising bandit instances. which are defined as:
"f(n) (n) 2 (n) m(P)
(117)
p (n) p(n)
(118)
12 (n) {
(p(n) (P())
if - otherwise
(119)
where P= (2 -2- and 0 (P)) will be specified later. In this setting, define 8 as follows:
s= 1 $2}
(120)
where {1} and S2 {2). Similar Theorem define:
M E - = "
(121)
We note that 4 A and f B belongs to A'. We firstly assume that the optimal super arm for μ is S2 and the optimal super for fe" is S1. We will show that it true after is specified.
22
(PP)
P
T
f1
((P)
P
T
The main idea of the proof is that for any arbitrary policy , the agent receives the same rewards for both ' and B at least until P, indicating that:
Rew (x', P) Rew, (
(122)
Problem (A) For A the optimal policy 7 selecting S2, for every time. The corresponding cumulative reward is given by:
Rew (T T) = F(T):
(123)
For the given policy x, the cumulative reward is upper bounded as follows:
T-B B_ [Ns,.]]
Rew (TT, T) = (n(P) - <) Ru [Ns.r] +
(n)
(124)
< (p P) $) M + F(T - M);
(125)
where equation 125 holds since the cumulative reward is maximized as E,A,, [Ns, minimized and it is guaranteed that (Ns,, 2
With The cumulative regret lower bounded by:
Reg (T,, T) F(T) (μ(P) -e) e) M
F(T M)
(126)
25

---

Published as a conference paper at ICLR 2026
Problem (B) For nº the optimal policy Th is selecting S1, for every time. The corresponding cumulative reward is given by:
Rew # (T T) -
(127)
For the given policy the cumulative reward is upper bounded as follows:
T-B RB [N
- Rew n - -) E
(2)
(128)
(u(()) - c) (T - - P M) + Σ
112 B
(n)
(129)
= (v(P)) - (T P M) + F(P M)
(130)
where equation 129 holds since the cumulative reward maximized as En . [Ns,.r] maximized and it is guaranteed that En in [Ns.rr T - P + Bu [Ns = T P M.
The cumulative regret is lower bounded by:
Reg,n (Tz, T) (n(P) =eT (n(PP) e) (T - P) F(P- M)
(131)
(m(P)- - (P- (P
(132)
From previous results, the worst-case regret can be lower bounded as follows:
inf sup Reg,, (T,,
(133)
x 1
2 inf max {Reg (T, T), Reg aT,
(134)
-inf max
(135)
MME(U.P)
F(T) - -1-
inf M.[0.P)
(136)
2
where equation 136 holds since max(a, b) a+b We observe that equation 136 is unimodal over
P. which means that it increases to maximum value and then decreases. More precisely, let A(n) == F(T) F(T n)) F(P n) (u(P) e) 2n). Then, have:
A(n + 1) Am) = F(T n) - F(T n F(P - n) - F(P n + 1) - 2(H(P) -E)
(137)
=M(T + 1) + p n 1) 2(x(PP) -),
(138)
which means that A(n) is concave, which means that A(n) is unimodal. It implies that:
F(T) F(T M) F(P- - (M)) + (M(P) - =E - -2M)
inf M)
(139)
2
min (u(P) - P F(P) F(T) - F(T -) (M(P) - P)
(140)
2
2
equation 140 consists of two terms: the first term obtained by setting M = 0 and the second term obtained by setting M P.
To calculate two terms, we use the property monotone functions.
Proposition 1. If a and b are integers with a < b and f is some real-valued function monotone
[a, b), we have:
[mn & Σ f(m) - -. f(t) dt max(f(a),(())
(141)
==a
Proposition indicates that we can bound p(n) and F(n) as follows:
m(n)= <
(x + 1) - dr + -
(142)
(21-c - (n+ 1))-1) + -
(143)
26

---

Published as a conference paper at ICLR 2026
For simplicity, we denote (2 - c)= by a so that p= aT. Then, we have:
(m(P)) - P) -P-FF F(P)
(144)
P
P
(++ + 1)-c - Pe- Σ
n) 1)
(145)
==1
==1
P
(n 1)(n 1)-c Pe
(146)
==1
2 pp--c_ Pe
(147)
(oT)E. - -
(148)
Similarly, we have:
F(T) F(T - P) (u(P) P)P
(149)
1
T-P
(1+1-n) + 11 Σ
(T - TT-Pt1--na+t (M(P) - P)
(150)
R=1
T
T-P
=
Σ (T+1-n)(n+1) +
Σ
+1 + 1)-
- (M((P) - E)P
(151)
R=T-P+1
n=1
+) () P - 1) (n(P) P
(152)
221-c
(aT + 1)2-c
[T) + (T aT) aT 1) -0
+ 2
aT
c- c-1
(153)
=c, + +) + EaT
(154)
where Now, we define so that equation 148 equals equation 154:
2alIss (c2 22- + o(T2-9)
(155)
Then, by substituting E to equation 148 and equation 154, we have: Reg, (T, T) 2 2 97
(156)
Now, we expand Lemma 4 to general combinatorial setting. Let be an arbitrary constant. As before, we define two problem f A. and μ B.L construct super arm set Sy, as follows:
"4 A.L (n) 14 (n) = ((P) e, iE [T],
(157)
"
A.L (n) =m(n,, ie 1,2LL
(158)
B.L (n) [u(n) if P
14
(M(P) otherwise
i E + 1,2L],
(159)
Sr. = {(a), (e,,,,,,,.,,,)) ar.: :a E [i, ie [
(160)
Due to same reason in Appendix C.4 we have:
inf sup Reg, (m, T) 2 Q(IT2-9)
(161)
HEA.
Now, we note that any stationary bandit problem is included in Ac, since (n) 0 for all base arm i E [K]. Previous literature has proven that for stationary bandit problem, the worst-case regret lower bound is (2V K)) (Lattimore & Szepesvári, 2020). Similarly, we can extend this setting to combinatorial setting:
inf sup Reg, (T, (T,T) 2 9(LVT).
(162)
t ued=
Combining these results, we conclude:
min max Reg, f. (T, T)) 2 Ω max { LVV, LTT-))) MEA.
(163)
27

---

Published as a conference paper at ICLR 2026
D PSEUDOCODE AND DESCRIPTION OF BASELINES
In Section 6, we have considered baseline algorithms to evaluate CRUCB's performance. Each al- gorithm is carefully chosen highlight different aspects of the bandit problem, such rising rewards and combinatorial settings. In this section, we provide the pseudocode and detailed descriptions for each baseline algorithm.
D.1 R-ED-UCB (METELLI ET AL., 2022)
R-ed-UCB is rising bandit algorithm that employs a sliding-window approach combined with UCB-based optimistic reward estimation algorithm, specifically designed for rising rewards. While it shares the core estimation method (t)) with CRUCB, R-ed-UCB applies this method directly to super arms and selects the maximum one, rather than applying it to base arms and solving the combinatorial problem in CRUCB. R-ed-UCB would be less effective in complex environments where the number super arms significantly exceeds the number of base arms, as it does not benefit from the shared exploration of common base arms, leading reduced exploration efficiency.
Algorithm 2 Rested UCB (R (R-ed- eC-UCB)
Input No,0 + 0 for all E [[S]], Sliding window parameter E. Initialize Play each super arm S, two times for each E [[S]]. for /, (1....:7) do
Calculate Future-UCB (t( for each super arm. S: e Solver (t), (t....... (t)) Play St and observe reward Rg.
Update F, and No,-
end for
D.2 SW-UCB (GARIVIER MOULINES, 2011)
SW-UCB is non-stationary bandit algorithm that uses sliding-window approach with UCB algorithm. estimates the reward of each super arm and confidence bounds using the following expressions:
N
A 1S0-U (1)
Σ
X²(1)
(164)
INN,r-1-h4 A+1
3 3logt
(SN-UCR(() (1)
(165)
2N
SH- (t) A. 003 (t) + (,K--UB
(166)
While the SW-UCB algorithm is similar to R-ed-UCB, it differs slightly in the values it estimates. Additionally, SW-UCB uses fixed sliding window size, in contrast to the dynamic sliding window size employed by R-ed-UCB, Similar to R-ed-UCB, SW-UCB would be less effective in complex environments.
Algorithm 3 sliding Window- UCB (SW-UCB)
Input Noo +- for all E [[S]] Sliding window size h. Initialize Play each super arm S, two times for each E [[S]]. for /. E (1....,7) do
For each super arm S., set (-s--uc UCB (t) 1..5 UCB (1) + 3398
UCB (t).
S, arg max( UCB (t), dow UCB UCB( ..) .439 GCD (t))
Play S; and observe reward Xs. (t).
Update a (NN-UC((1) (1) and No,.
end for
28

---

Published as a conference paper at ICLR 2026
D.3 SW-CUCB (CHEN ET AL., 2021)
SW-CUCB is non-stationary combinatorial bandit algorithm that uses a sliding-window approach with UCB algorithm for combinatorial setting. It estimates the values 13 j (L) and 8 1E* (t), which are nearly identical to those used in SW-UCB but specifically adapted for base arms. SW-CUCB
then utilizes Solver address the combinatorial problem.
Algorithm 4 s sliding Window Window-Combinen www.-natoiiiniiiiccmmcmmmmaa UCB (SW-CUC3)
Input Ne. 0 for all E [K]. Sliding window size h. Initialize Play arbitrary super arm including base arm two times for each i [K].
for 1. (1,...:7)) do
For each base arm i, set f CUCB (L) 11 CUCD (1) + 3:th CUCD (1). ASV-CUCa (t)).
Solver(ús (t), 122 (ig--cu=((t)) (t),... PK
Play S. and observe reward (t)(t).
Update p 2 (iN-CUCB(() (t) and N..-
end for
D.4 SW-TS (TROVO ET AL., 2020)
SW-TS is non-stationary bandit algorithm that uses a bldding-window approach with Thompson Sampling. Since outcomes are bounded, the algorithm updates the parameters by adds Xs, (t) to and Xs. (t) to based on the observed output Xs, (t). SW-TS also utilizes fixed sliding window size similar to SW-UCB. Similar to R-ed-UCB and SW-UCB, SW-TS also operates directly on super arms, it may suffer from reduced exploration efficiency in complex environments.
Algorithm 5 Sliding Window Thompson Sampling (SW-TS)
Input Sliding window size h. Initialize Play each super arm S, two times for each E [[[]].
for 1. (1....; T) do
For each super arm S; set (t(t) ~ Betala; + +1,3 + 1). arg max(0) (t), 02()). (t)).)
Play S, and observe reward Xs.
Update a and B,.
end for
D.5 SW-CTS
SW-CTS is non-stationary combinatorial bandit algorithm that uses sliding-window winddw approach with Thompson Sampling for combinatorial setting. While it operates similarly to SW-TS, the key difference is that SW-CTS performs estimation base arms then solves the combinatorial problem using Solver.
Algorithm Sliding Window- Bonddow-Combinntoiiia. Thompson Sampling (SW-CT))
Input Sliding window size
Initialize Play arbitrary super arm including base arm two times for each i [K]. for t E (I...., T') do
For each base arm i, set (t( Beta(a; + 1, 1). S. < Solver(O (t), (t), .(0)((()))))) Play S, and observe reward Xs. (t).
Update as and Br.
end for
29

---

Published as a conference paper at ICLR 2026
E EXPERIMENTAL DETAILS
Table 1: Overview of task specifications. We summarizes the details of each task, including the number of base arms K, the number of super arms |S], and the maximal size of a super arm L.
Environment
Experiment
difficulty
K
[S]
L
toy
3
2
Online shortest path
easy
12
Synthetic environments (Section 6.1 & Appendix F)
complex
60
252
10
Maximum weighted matching
easy
8
12
2
complex
28
840
4
Minimum spanning tree
easy
6
3
complex
15
1296
k-MAX
5
10
2
Deep reinforcement learning (Section 6.2)
AntMaze-easy
7
5
AntMaze-complex
48
178
15
Table 2: Hyperparameters for AntMaze Tasks.
AntMaze-casy
AntMaze-complex
number of graph nodes fail condition
6
16
100
100
maximum length of episode
500
1000
2000
3000
hidden layer actor critic
(256, 256)
(256, 256)
0.0001
0.0001
0.001
0.001
0.005
0.005
0.99
0.99
batch size
1024
1024
In Section 6, we conduct experiments in two distinct environments: synthetic environments and deep reinforcement learning settings. This section provides a detailed description of each environment, including their design and hyperparameters. The specifications for each experiment are summarized Table
E. SYNTHETIC ENVIRONMENTS
In the synthetic environments, we have the flexibility to design reward functions by choosing arbitrary values. Here, we set c 1.2, which lies the range between and 1.5. This choice is motivated by the theoretical reasoning discussed in Section 5. To be specific, ((2) ([T
Tooo + +1] 1000 + 1) -1.2 for n 20000 and for n > 20000 with a 0.01. In the simpler environments, we use (n) = (I
250 1) for 5000 and 0 for 5000. As depicted in Figure 3, the regret upper bound for these environments is O(T ), and the regret lower bound O(T0.8). Therefore, while the regret observed in Figure 5b appears nearly linear, which aligns with the theoretical bounds, still demonstrates superior performance compared to other baseline algorithms.
E.2 DEEP REINFORCEMENT LEARNING
In the deep reinforcement learning environments, conducted experiments using the AntMaze environment. AntMaze a hierarchical goal conditioned reinforcement learning task where an ant robot navigates predefined goal hierarchically. The ant robot in this environment has four legs,
30

---

Published as a conference paper at ICLR 2026
each with two joints, resulting in action space that controls total of eight joints. The reward structure for the low-level agent is simple: the agent receives a reward of when it reaches the goal comes within certain distance of it, and reward of 1 otherwise. Our experiments are carried out in the scenario depicted in Figure 5, which shows the map and corresponding graph structure used. To ensure consistent and repeated exploration over the fixed graph, utilized code based on the algorithm described in (Yoon et al., 2024) without the adaptive grid refinement. The hyperparameters used in these experiments are summarized in Table 2.
In each experiment, the algorithm generates a path that the ant robot follows, receiving feedback based on success or failure. For combinatorial methods, the agent does not persist with single edge until the episode ends; if the agent fails to reach the goal within 100 steps, the attempt is considered failure. In this case, the reward is set to and the agent fails to attempt the next edge, which known as the cascading bandit setting. If the agent successfully reaches the goal, the reward is proportional to the efficiency, calculated as the number of steps taken divided by 100. For non-combinatorial methods, the reward for success is determined by the number of steps taken divided by the maximum length the episode. We note that while the reward function AntMaze is non-concave, as depicted in Figure 7a, and cascading bandit setting, confirmed that RCUCB performs well, illustrated in Figure 7.
31

---

Published as a conference paper at ICLR 2026
F ADDITIONAL EXPERIMENTS
In this section, we present additional experiments to evaluate the performance of CRUCB broader of environments. Specifically, we test CRUCB on three representative combinatorial optimization problems, k-MAX (Section F.1), maximum weighted matching (Section F.2), and minimum spanning tree (Section F.3). These experiments demonstrate that CRUCB maintains strong performance across diverse scenarios, further validating its robustness and adaptability.
F.1 M-MAX TASK
We investigate the k-MAX setting, where the reward is determined by the maximum value among outcomes of the selected base arm. As shown in Theorem the optimal policy for the k-MAX may not always involve consistently pulling a single super arm. However, since the k-MAX satisfies the aduitive-bounded reward assumption in Theorem 2 with B,, Vे By optimal constant policy (consistntly pulling (1, 5)) to calculate regret.
approximate
x10*
1.0
CRUCB (Durs)
R-ed-UCB
0.8
SW-CUCB
outcome
0.6
regret
1
SW-UCB
0.4
SW-CTS
0.2
SW-TS
0
20K number of pulls
0
100K
200K
300K
episode number
(a) Outcome functions
(b) Cumulative regret
Figure 9: k-MAX task. (a) Reward functions (c = 1.2) for base arms 1-5, where K and 2. (b) Regret curves for K-MAX. Lines show average; shaded areas indicate 99% confidence intervals over 5 runs.
The results, as shown Figure 9b, demonstrate that CRUCB consistently outperforms other algo- rithms. R-ed-UCB shows sub-optimal regret due the partially shared enhancement. Notably, we observe that among non-stationary algorithms, combinatorial algorithms (SW-CUCB, SW-CTS) perform worse than combinattaat algorithms (SW-UCB, SW-TS). Non-combinatorial algorithms select the early peaker (5) frequently while evenly exploring other edges. On the other hand, combi- natorial algorithms select early peakers (4, 5), limiting exploration of late bloomers and preventing them from fully rising their potential.
32

---

Published as a conference paper at ICLR 2026
F.2 MAXIMUM WEIGHTED MATCHING
We conduct experiments on maximum weighted matching task, a widely studied classic combinatorial optimization problem. In this task, to find a matching where each node u, E U is paired with a unique node vy E V, ensuring no overlapping connections. The objective is to maximize the total reward by selecting the best set of edges between these nodes.
given disjoint sets of nodes, U and V, and the goal
1.0
1.0
0.8
0.8
outcome
outcome
0.6
0.6
0.4
0.4
0.2
early peaker
0.2
early peaker
bloomer
late bloomer
0
0 10K 20K30K4KK 50K number pulls
D 10K 20K 30K40K50K
number of pulls
(a) Matching-ean,
(b) Outcome functions
(c) Matching-complex
(d) Outcome functions
Figure 10: Maximum weighted matching task. (a, c) Graphs used to evaluate CRUCB and baselines. (b, d) Corresponding outcome functions for each task.
x10
x10*
CRUCB (Durs)
R-ed-UCB
SW-CUCB
regret
regret
SW-UCB
1
SW-CTS
SW-TS
0
0
0
100K
200K
300K
0
250K
500K
episode number
episode number
(a) Matching-easy
(b) Matching-complex
Figure 11: Cumulative regret in maximum weighted matching task. Regret curves for (a) Matching-easy and (b) Matching-complex. Lines show average; shaded areas indicate 99% confidence intervals over runs.
We use the same outcome function in the online shortest path problem, shown Figure 10b and The graph structures are depicted in Figure 10a and c. The regret results, shown in Figure 11, confirm that CRUCB outperforms the baseline algorithms in this task.
The task is particularly relevant in settings like job matching, where each job can be matched to a worker, and the reward might increase over time as workers gain experience. This makes the problem perfect fit for combinatorial bandit settings, where the rewards of certain matches (such as experienced workers with higher skill levels) rise as more interactions occur, highlighting the rising aspect of the task.
33

---

Published as a conference paper at ICLR 2026
F.3 MINIMUM SPANNING TREE
We conduct experiments on minimum spanning tree task, fundamental problem in combinatorial optimization, where the objective is to find subset of edges that connect all nodes in graph with the minimum total edge weight, ensuring no cycles. However, in our setting, we treat the weight of each edge outcome, meaning we aim maximize the total outcome, which is equivalent to minimizing the total edge weight.
1.0
1.0
0.8
0.8
outcome
outcome
0.6
0.6
0.4
0.4
0.2
0.2
late bloomer
late bloomer
10K 2KK
10K 30K40K50K
number pulls
number pulls
(a) Spanning-ean eass
Outcome functions
Spanning-comple
(d) Outcome functions
Figure 12: Minimum spanning tree task. (a, c) Graphs used to evaluate CRUCB and baselines. (b. d) Corresponding outcome functions for each task.
x10*
X10*
CRUCB (Ours)
R-ed-UCB
SW-CUCB
regret
regret
SW-UCB
1
SW-CTS
SW-TS
0
0
0
100K
200K
300K
0
250K
500K
episode number
episode number
(a) Simple graph
(b) Complex graph
Figure 13: Cumulative regret in minimum spanning tree task. Regret curves for (a) Spanning-easy and (b) Spanning-complex Lines show average; shaded areas indicate 99% confidence intervals over 5 runs.
Similarly, evaluate minimum spanning tree task with the same outcome function from Figure 12b and d, applied to the graph structures in Figure 12a and c. The regret results, presented Figure 13, indicate that CRUCB consistently performs better than the baselines.
This formulation is particularly relevant practical applications such as network routing, where objective is to establish efficient communication across a distributed system. Over time, as certain paths are used more frequently, the network can adapt and optimize its behavior: caches warm up, congestion reduces through load balancing, and routing protocols fine-tune their decisions. As result, the effective cost using the same edge decreases, which translates into a rising reward for that edge.
34

---

0.4 Published as a conference paper at ICLR 2026
F.4 SENSITIVITY TO THE WINDOW SIZE PARAMETER
To evaluate the robustness of CRUCB to the choice of the window size hyperparameter e, we conducted sensitivity analysis in the Path-easy environment (described in Section 6.1). We compared the cumulative regret at different episode counts for values of 0.05, 0. 0.125, 0.25, and 0.4.
Table 3: Cumulative regret at different episodes for various values in the Path-easy task.
Regret
= 0.05
0.125
0.25
100K
8019.34
8020.53
8020.53
8019.64
200K
13715.91
13717.10
13717.10
13716.21
300K
19060.71
19061.90
19061.90
19061.01
The results, summarized in the table below, show that the performance of CRUCB remarkably stable across this wide range of values, indicating that our algorithm is not overly sensitive this hyperparameter choice in practice.
35

---

Published as a conference paper at ICLR 2026
G
HEATMAPS IN ANTMAZE-COMPPEX
Less visited
More visited
t= 100
t= 500
t= 3000
(a) Optimal
(b) CRUCB
(c) R-ed-UCB (d) SW-CUCB (c) SW-UCB (f) SW-CTS
(g) SW-TS
Figure 14: Heatmap illustrating visit frequencies in AntMaze-complex. We visualize the visit frequencies for the optimal policy, CRUCB, and baseline algorithms. The heatmap includes three rows representing visit frequencies until episode numbers 100, 500, and 3000.
In Figure 14, we provide a more comprehensive view by illustrating the exploration patterns across all baseline algorithms at various stages. The optimal policy, which follows the oracle constant policy, only explores the optimal path from the start to the goal, resulting in highly focused exploration along this path, as depicted in Figure 14a. Figure 14b, CRUCB exhibits exploration patterns most similar the optimal policy compared to other baselines, demonstrating its efficiency in targeting the goal effectively. Among the baselines, SW-CTS notably aligns most closely with the optimal policy in the exploration patterns and the only algorithm to show significant difference in regret compared to the others, as seen in Figure 7c. In comparison, algorithms not specifically designed for combinatorial settings, such R-ed-UCB, SW-UCB, and SW-TS, suffer from less efficient exploration. Their exploration resembles breadth-fire search pattern, as they must explore broader range of super arms despite having given goal.
In Figure 15 and Figure 16, we further analyze the exploration behaviors of each algorithm by visualizing their try frequencies at both the path and edge levels. The optimal policy concentrates its tries exclusively along the shortest path, resulting in highly localized activity in both visualizations. CRUCB exhibits exploration patterns that closely resemble those of the optimal policy, maintaining focused and structured exploration throughout. Notably, AntMaze-complex includes 178 possible paths, which makes exhaustive exploration highly tone-consuming. As illustrated Figure 15, non-combinatorial algorithms struggle with this complexity: by episode 100, some paths remain untried, and even by episode 3000, their exploration remains broadly distributed and unguided, indicating inefficient use of the exploration budget.
36

---

Published as a conference paper at ICLR 2026
Less tried
More tried
t= 100
geal
goal
pool
ooal
goal
goal
goal
t= 500
t= 3000
(a) Optimal
(b) CRUCB
R-ed-UCB (d) SW-CUCB (c) SW-UCB (f) SW-CTS
(g) SW-TS
Figure 15: Heatmap illustrating the path-level try frequencies in AntMaze-comples We visualize the path-level try frequencies for the optimal policy, CRUCB, and baseline algorithms. The heatmap
includes three representing the lath-level try frequencies until episode numbers 100, 500, and 3000.
Less tried
More tried
== 100
2031
0631
0O0
t= 500
t= 3000
(a) Optimal
(b) CRUCB
(c) R-ed-UCB (d) SW-CUCB (e) SW-UCB (l SW-CTS
(g) SW-TS
Figure 16: Heatmap illustrating the edge-level try frequencies in AntMaze-comples We visualize the edge-level try frequencies the optimal policy, CRUCB, and baseline algorithms. The heatmap
includes three rows representing the edge-level try frequencies until episode numbers 100, 500, and 3000.
37

---

Published as a conference paper at ICLR 2026
H THE USE OF LARGE LANGUAGE MODELS (LLMS)
In the preparation of this manuscript, we utilized large language model (LLM) as a writing assistant aid in polishing the text. The LLM's role was limited to refining phrasing and grammar in author- written drafts, suggesting alternative sentence structures to improve clarity, and helping maintain consistent academic tone. All technical contributions, theoretical results, experimental designs, and final claims were conceived and developed solely by the human authors. The authors thoroughly reviewed and edited the manuscript and take full responsibility for all content presented this paper.
38


Reviews:
[{"review_id": "v6GLvienrf", "reviewer": "Reviewer_obpT", "summary": "The authors propose a combinatorial rising bandit algorithm that handles cases where the expected reward of each base arm increases over time in a combinatorial setting. The paper is theoretically solid, providing both regret lower and upper bounds based on the proposed UCB-based algorithm. Simulations and the shortest-path problem both demonstrate the performance of the proposed approach. Overall, I think this is a well-written paper with enough detail to support its claims.", "questions": "1. I’m curious whether the authors have considered extending the framework to a Thompson Sampling (TS)-based algorithm under this setting. I saw that the simulations include TS baselines. While I understand that CRUCB should perform better since it is specifically designed to handle both the combinatorial and rising-reward aspects, I’d be interested to hear how the authors view the challenges of extending this to a TS version, since TS often slightly outperforms UCB in many settings.\n2. In Theorem 3, I don’t quite understand the meaning of q. Does the theorem hold for any q \\in [0,1], or is it a pre-specified value determined from upstream? How is q decided in practice?\n3. What is the general computational complexity of the algorithm? I’m curious which part dominates the computation time: is it the combinatorial optimization part (the solver in CRUCB) or the rising reward evaluation part (Future-UCB calculation)? Either a theoretical complexity order or an empirical runtime illustration would be helpful.\n4. It would also be nice if the authors could provide more examples or motivating scenarios showing where combinatorial rising bandit problems are commonly encountered.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well structured, with a clear flow and proper introduction of concepts, making it easy to follow even for readers who may not work directly in this area.\n2. The theoretical results are sound. I think this problem is genuinely challenging given both the combinatorial nature and the non-stationary reward that changes as arms are pulled over time. The authors set a good pace to introduce the theoretical results.\n3. The simulation part is clear and effectively supports the theoretical findings.", "weaknesses": "See Questions below.", "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": "bg8cPDEtsy", "reviewer": "Reviewer_hg9R", "summary": "This work studies a MAB setting where it combines two existing setting Combinatorial bandits (gets selected a set of arms) in each round and the arms also gets better in each round. The setting poses an interesting challenge where in which the optimal policy has to balance out with good early pieces and late bloomers. They propose a new UCB style algorithm, CRUCB that takes into account of future reward and constructing a upper bound for each arm and according selecting the best arm. They provide regret theoretical guarantees for this algorithm complemented by experiments on different scenarios.", "questions": "1. Does CRUCB suffer any extra cost from the Solver as compared to the greedy selection of arm  ? So, by treating Solver as a oracle that exist, is there any cost that is not accounted in the regret ?\n\n2. In case, if the $\\mu_i(n+1) - \\mu_i(n) = 0$, Does the setting reduce to a Standard Combinatorial algorithm ? and how does the regret compare against other existing Combinatorial algorithms ? Can you provide which term in Theorem 3 is unavoidable in comparison to those algorithm ? \n\n3. Also, if each super arm is exclusively just the base arm and the $|S|$ = $K$, so does the setting reduces to a rising bandits then in that case as there is an assumption of concavity of $\\mu_i$, how does CRUCB's regret compare against the rising bandits algorithm ? Does CRUCB recovers the regret for rising bandits ?\n \n4. Many practical scenario involve piecewise rising (i.e. the reward rise with pulls, gets stagnant for a period and then rise), does violating Assumption 1 breaks the regret guarantee ?\n\n5. Does Regret bound in Theorem 3 becomes sublinear if the rising effect did not become saturated ?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The work introduces a new bandits setting that combines combinatorial and rising bandits. The setting is interesting and seems to have a wide range of application.\n\nThe authors proposed a new algorithm CRUCB for this setting showcase its performance with a regret upper bound in $K$ and $L$. \n\nThe work also includes a lower bound to highlight the difficulty of this setting and to further complement the results of CRUCB's regret upper bound. \n\nThe authors provide a good experimental setup to validate CRUCB in shortest planning task and hierarchical RL tasks comparing against baselines in rising and combinatorial baselines.", "weaknesses": "The Solver is treated as an oracle that exist to solve this combinatorial problem and cost associated is not discussed. \n\nMany combinatorial tasks in real world practice exhibits non-monotonic rewards but the work assumes $r$ as a monotonic function. The assumption of reward formulation being monotonic in $S$ \\& $\\mu$ limits its use case and generality.  \n\n*also refer questions section.", "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": "wiXL6KCI85", "reviewer": "Reviewer_GnsM", "summary": "This work makes the first step to study the combinatorial rising bandit problem, where the mean of the chosen base arm in round $t$ will increase in round $t+1$. The authors propose the Combinatorial Rising UCB (CRUCB) algorithm, the core of which is to use a UCB constructed using the empirical mean from the latest sliding window, the exploration bonus, and the predicted improvement. Both regret upper bound and the lower bound are established for the proposed algorithm. Experiments on synthetic environments and deep reinforcement learning settings are conducted.", "questions": "1. As the reward of some chosen base arm $i$ in round $t$ will increase in round $t+1$, this problem seems a special case of adversarial bandits with an adaptive adversary. In this view and assuming $ r(S, \\boldsymbol{\\mu}) =\\sum_{i\\in S}\\mu_i$, I think that the algorithms in previous works for adversarial combinatorial bandits with semi-bandit feedback (say, [3,4]) are applicable to this problem and that $O(\\sqrt{T})$ regret upper bound is achievable. However, when $ f(n)=(n+1)^{-c}$ and $c=1.1$, this seems to contradict the lower bound of $\\Omega(T^{2-c})=\\Omega(T^{0.9})$. Do I miss something?\n\n[3] Audibert et al. Regret in online combinatorial optimization. Mathematics of Operations Research, 13.\n\n[4] Zimmert et al. Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously. ICML, 19.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This seems to be the first work in the literature to model and resolve the combinatorial rising bandit problem.\n2. The paper is generally well-written.", "weaknesses": "1. **Novelty**: Though the problem formulation is relatively new, the technical novelty seems somewhat limited. To me, the core part of the proposed algorithm is to use a UCB constructed using exploration bonus, the empirical mean, and the predicted improvement in the past sliding window, which is exactly the way [1] deals with rising multi-armed bandits (MABs). Of course, their method cannot deal with the combinatorial rising bandit problem. However, it is not clear to me whether there are additional technical difficulties when combining the method to deal with rising MABs and non-rising combinatorial bandits (say, [2]). As such, this prevents me from giving a positive rating for this work. And due to my relatively limited expertise in combinatorial bandits, I’d like to maintain a low level of confidence in my rating.\n\n[1] Metelli et al. Stochastic Rising Bandits. ICML, 22.\n\n[2] Chen et al. Combinatorial multi-armed bandit with general reward functions. NeurIPS, 16.", "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": "gcJ1XrE7Zf", "reviewer": "Reviewer_zJJk", "summary": "This paper studies combinatorial semi-bandits with rested rising rewards, a setting relevant to diverse application domains such as robotics and maintenance scheduling. To address this problem, the authors propose the CRUCB algorithm and provide corresponding regret guarantees. They further demonstrate the effectiveness of the method through empirical evaluations.", "questions": "1. Could the authors elaborate on the unique challenges of incorporating rising rewards into the combinatorial semi-bandit setting? It is not fully clear what makes this extension technically difficult compared to standard combinatorial or rising bandits.\n\n2. The novelty of the proposed algorithm relative to prior work on rising bandits is not fully articulated. A more explicit comparison against existing methods (e.g., in the algorithm section) would better highlight the contribution.\n\n3. The discussion on effective window size remains insufficient. In particular, the choices of window parameters for equations (10), (11), and (12) are not explained, and it is unclear how these influence theoretical guarantees or empirical performance.\n\n4. Regarding the experimental setup:\n   - How were the window sizes selected for the sliding-window type baselines?\n   - How was  R-ed-UCB (with bandit feedback) adapted to the combinatorial semi-bandit feedback model?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper is the first to consider combinatorial semi-bandits with rising rewards.", "weaknesses": "1. My main concern is the novelty of the proposed algorithm. The paper does not clearly identify what non-trivial challenges arise specifically from incorporating rising rewards into the combinatorial semi-bandit setting, nor how the approach fundamentally differs from existing methods for rising or combinatorial bandits.\n\n2. It is unclear whether the presented regret bound is tight.\n\n3. The role of window sizes and their effect on performance is not discussed. Providing guidance or theoretical justification for the choice of window size would strengthen the practical relevance of the method.", "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)