Towards More Efficient, Robust, Instance-adaptive, and Generalizable Sequential Decision making

Zhiyong Wang

cs.LGApr 12, 2025

Towards More Efficient, Robust, Instance-adaptive, and Generalizable Sequential Decision making

Authors: Zhiyong Wang

Organizations: Department of Computer Science and Engineering, The Chinese University of Hong Kong

Abstract

The primary goal of my Ph.D. study is to develop provably efficient and practical algorithms for data-driven sequential decision-making under uncertainty. My work focuses on reinforcement learning (RL), multi-armed bandits, and their applications, including recommendation systems, computer networks, video analytics, and large language models (LLMs). Sequential decision-making methods, such as bandits and RL, have demonstrated remarkable success - ranging from outperforming human players in complex games like Atari and Go to advancing robotics, recommendation systems, and fine-tuning LLMs. Despite these successes, many established algorithms rely on idealized models that can fail under model misspecifications or adversarial perturbations, particularly in settings where accurate prior knowledge of the underlying model class is unavailable or where malicious users operate within dynamic systems. These challenges are pervasive in real-world applications, where robust and adaptive solutions are critical. Furthermore, while worst-case guarantees provide theoretical reliability, they often fail to capture instance-dependent performance, which can lead to more efficient and practical solutions. Another key challenge lies in generalizing to new, unseen environments, a crucial requirement for deploying these methods in dynamic and unpredictable settings. To address these limitations, my research aims to develop more efficient, robust, instance-adaptive, and generalizable sequential decision-making algorithms for both reinforcement learning and bandits. Towards this end, I focus on developing more efficient, robust, instance-adaptive, and generalizable for both general reinforcement learning (RL) and bandits.

Figures & tables

\displaystyle\widehat{\mathcal{P}}^{k}=\left\{P\in\mathcal{P}:\sum_{s,a,s^{\prime}\in\mathcal{D}}\log P(s_{i}^{\prime}|s_{i},a_{i})\geq\max_{\tilde{P}\in\mathcal{P}}\sum_{s,a,s^{\prime}\in\mathcal{D}}\log\tilde{P}(s_{i}^{\prime}|s_{i},a_{i})-\beta\right\}.

Algorithm 1 Optimistic Model-based RL (O-MBRL)

\displaystyle\widehat{\mathcal{P}}=\left\{P\in\mathcal{P}:\sum_{i=1}^{n}\log P(s_{i}^{\prime}|s_{i},a_{i})\geq\max_{\tilde{P}\in\mathcal{P}}\sum_{i=1}^{n}\log\tilde{P}(s_{i}^{\prime}|s_{i},a_{i})-\beta\right\}.

Algorithm 2 ( [ 218 ] ) Constrained Pessimistic Policy Optimization with Likelihood-Ratio based constraints (CPPO-LR)

Algorithm	Suboptimality Gap
PERM (our Algo. 4 )	$\sqrt{\log(\mathcal{N})/n}+n^{-1}\sum_{i=1}^{n}\sum_{h=1}^{H}$ $\mathbb{E}_{i,\pi^{*}}\big[\Gamma_{i,h}(s_{h},a_{h})\,\big\|\,s_{1}=x_{1}\big]$
PPPO (our Algo. 5 )	$\sqrt{\log\|\mathcal{A}\|\,H^{2}/n}+n^{-1}\sum_{i=1}^{n}\sum_{h=1}^{H}$ $\mathbb{E}_{i,\pi^{*}}\big[\Gamma_{i,h}(s_{h},a_{h})\,\big\|\,s_{1}=x_{1}\big]$

Table 4.1 : Summary of our algorithms and their suboptimality gaps, where

\mathcal{A}

is the action space,

H

is the length of episode,

n

is the number of environments in the offline dataset. Note that in the multi-environment setting,

\pi^{*}

is the near-optimal policy w.r.t. expectation (defined in Section 8.2 ).

\mathcal{N}

is the covering number of the policy space

\Pi

w.r.t. distance

\mathrm{d}(\pi^{1},\pi^{2})=\max_{s\in\mathcal{S},h\in[H]}\|\pi^{1}_{h}(\cdot|s)-\pi^{2}_{h}(\cdot|s)\|_{1}

. The uncertainty quantifier

\Gamma_{i,h}

are tailored with the oracle return in the corresponding algorithms (details are in Section 4.4 ).

Panel of Figure 4 — Figure 4.1 : Two Contextual MDPs with the same compliant average MDPs. The discrete contextual space is defined as $C=\{v,w\}$ and both MDPs satisfies $\mathcal{S}=\{x_{1}\},\mathcal{A}=\{a_{1},a_{2},a_{3}\},H=1$ . The data collection distributions $\mu$ and rewards $r$ for each action of each context are specified in the graph.

\displaystyle\textstyle{\overline{\bm{M}}_{\overline{V}_{t},t-1}=\lambda\bm{I}+\sum_{i\in\overline{V}_{t}}\bm{M}_{i,t-1}\,,\overline{\bm{b}}_{\overline{V}_{t},t-1}=\sum_{i\in\overline{V}_{t}}\bm{b}_{i,t-1}\,,\hat{\bm{\theta}}_{\overline{V}_{t},t-1}=\overline{\bm{M}}_{\overline{V}_{t},t-1}^{-1}\overline{\bm{b}}_{\overline{V}_{t},t-1};}

Algorithm 7 Robust Clustering of Misspecified Bandits Algorithm (RCLUMB)

Figure 6.1 : Illustration of LOCUD. The unknown user relations are represented by dotted circles, e.g. , user 3, 7 have similar preferences and thus can be in the same user segment ( i.e. , cluster). Users 6 and 8 are corrupted users with dynamic behaviors over time ( e.g. , for user 8, the behaviors are normal at $t_{1}$ and $t_{3}$ (blue), but are adversarially corrupted at $t_{2}$ and $t_{4}$ (red) [ 164 , 93 ] ), making them hard to be detected online. The agent needs to learn user relations to utilize information among similar users to speed up learning, and detect corrupted users 6, 8 online from bandit feedback.

\left\lVert\hat{\bm{\theta}}_{i_{t},t}-\hat{\bm{\theta}}_{\ell,t}\right\rVert_{2}\geq\alpha_{1}\big(f(T_{i_{t},t})+f(T_{\ell,t})+\alpha C\big)\,,

Algorithm 8 RCLUB-WCU

	$\displaystyle\left\lVert\tilde{\bm{\theta}}_{i,t}-\hat{\bm{\theta}}_{V_{i,t},t}\right\rVert_{2}$	$\displaystyle>\frac{\sqrt{d\log(1+\frac{T_{i,t}}{\lambda d})+2\log(\frac{1}{\delta})}\sqrt{\lambda}}{\sqrt{\lambda_{\text{min}}(\tilde{\bm{M}}_{i,t})+\lambda}}$
		$\displaystyle+\frac{\sqrt{d\log(1+\frac{T_{V_{i,t},t}}{\lambda d})+2\log(\frac{1}{\delta})}+\sqrt{\lambda}+\alpha C}{\sqrt{\lambda_{\text{min}}(\bm{M}_{{V}_{i,t},t})}}\,,$		(6.5)

Algorithm 9 OCCUD (At round

t

, used in Line 11 in Algo. 8 )

Panel of Table 6 — Table 6.1 : Detection results on synthetic and real datasets

Figure 7.1 : Experimental results on synthetic dataset

Figure 7.2 : Experimental results on real-word datasets

Alogrithm	Total time	Total time for selecting arms	Total time for selecting key-terms
ConUCB	11,297	5,217	6,080
ConLinUCB-UCB	5,738	3,060	2,678
ConLinUCB-MCR	4,821	3,030	1,791
ConLinUCB-BS	3,127	3,120	6

Table 7.1 : Total runninng time (in seconds) of algorithms on Movielens with

T=5,000

			Variance	Varying
Model	Algorithm	Regret	-Dependent	Arm Set	Require $B_{K}$
	SW-UCB
	[ 39 ]	$\tilde{O}\big(d^{\frac{7}{8}}B_{K}^{\frac{1}{4}}K^{\frac{3}{4}}\big)$	No	Yes	Yes
Linear Bandit	BOB
	[ 39 ]	$\tilde{O}\Big(d^{\frac{7}{8}}B_{K}^{\frac{1}{4}}K^{\frac{3}{4}}\Big)$	No	Yes	No
	RestartUCB

Table 8.1 : Comparison of non-stationary bandits in terms of regret guarantee.

K

is the total rounds,

d

is the problem dimension for linear bandits,

B_{K}

is the total variation budget defined in Section 8.2 (for the MAB setting,

B_{K}=\sum_{k=1}^{K}\|\mu_{k}-\mu_{k+1}\|_{\infty}

, where

\mu_{k}

is the mean of the reward distribution at round

k

V_{K}

is the total variance defined in Section 8.2 ,

\left|\mathcal{A}\right|

is the number of arms for MAB.

\displaystyle\bar{\sigma}_{k}\leftarrow\max\{\sigma_{k},\alpha,\gamma\|\mathbf{a}_{k}\|_{\hat{\bm{\Sigma}}_{k}^{-1}}^{1/2}\}

(8.3)

Algorithm 11 Restarted-

\text{WeightedOFUL}^{+}

\displaystyle\hat{\bm{\Sigma}}_{k+1,\ell_{k}}\leftarrow\hat{\bm{\Sigma}}_{k,\ell_{k}}+w_{k}^{2}\mathbf{a}_{k}\mathbf{a}_{k}^{\top},\hat{\mathbf{b}}_{k+1,\ell}\leftarrow\hat{\mathbf{b}}_{k,\ell_{k}}+w_{k}^{2}\cdot r_{k}\mathbf{a}_{k},\hat{\bm{\theta}}_{k+1,\ell_{k}}\leftarrow\hat{\bm{\Sigma}}_{k+1,\ell_{k}}^{-1}\hat{\mathbf{b}}_{k+1,\ell_{k}}.

Algorithm 12

\text{Restarted SAVE}^{+}

Panel of Figure 8 — Figure 8.1 : The regret of Restarted- $\text{WeightedOFUL}^{+}$ , $\text{Restarted SAVE}^{+}$ , SW-UCB and Modified EXP3.S under different total rounds.

	$\displaystyle\overline{\bm{\theta}}_{t}$	$\displaystyle=\text{argmin}_{\bm{\theta}}-\sum_{s\in[t-1]\atop i_{s}\in\overline{C}_{t}}\Big(y_{s}\log\mu\left({\bm{\theta}}^{\top}\left[\phi(\bm{x}_{s,1})-\phi(\bm{x}_{s,2})\right]\right)+(1-y_{s})\log\mu\left({\bm{\theta}}^{\top}\left[\phi(\bm{x}_{s,2})-\phi(\bm{x}_{s,1})\right]\right)\Big)$
		$\displaystyle\hskip 9.24994pt+\frac{\lambda}{2}\left\lVert\bm{\theta}\right\rVert_{2}^{2};$		(9.6)

Algorithm 13 Clustering Of Linear Dueling Bandits (COLDB)

Panel of Figure 9 — Figure 9.1 : Experimental results for our COLDB algorithm with a linear reward function.

Figure 9.2 : Experimental results for our CONDB algorithm with a non-linear (square) reward function.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

	$\displaystyle\bm{M}_{i_{\tau},\tau}$	$\displaystyle=\bm{M}_{i_{\tau},\tau-1}+\bm{x}_{a_{\tau}}\bm{x}_{a_{\tau}}^{\mathrm{T}},\bm{b}_{i_{\tau},\tau}=\bm{b}_{i_{\tau},\tau-1}+r_{\tau}\bm{x}_{a_{\tau}},$
	$\displaystyle T_{i_{\tau,\tau}}$	$\displaystyle=T_{i_{\tau},\tau-1}+1,\hat{\bm{\theta}}_{i_{\tau},\tau}=(\lambda\bm{I}+\bm{M}_{i_{\tau},\tau})^{-1}\bm{b}_{i_{\tau},\tau}$
	$\displaystyle\bm{M}_{V_{j},\tau}$	$\displaystyle=\bm{M}_{V_{j},\tau-1}+\bm{x}_{a_{\tau}}\bm{x}_{a_{\tau}}^{\mathrm{T}},\bm{b}_{V_{j},\tau}=\bm{b}_{V_{j},\tau-1}+r_{\tau}\bm{x}_{\tau},$
	$\displaystyle T_{V_{j},\tau}$	$\displaystyle=T_{V_{j},\tau-1}+1,\hat{\bm{\theta}}_{V_{j},\tau}=(\lambda\bm{I}+\bm{M}_{V_{j},\tau})^{-1}\bm{b}_{V_{j},\tau},$
	$\displaystyle\tilde{\bm{\theta}}_{V_{j},\tau}$	$\displaystyle=\frac{\sum_{i\in V_{j}}\hat{\bm{\theta}}_{i},\tau}{[V_{j}]}$

Appendix

Algorithm 15 Robust Set-based Clustering of Misspecified Bandits Algorithm (RSCLUMB)

	$\displaystyle\bm{M}_{V_{j},\tau}$	$\displaystyle=\bm{M}_{V_{j},\tau}-\bm{M}_{i_{\tau},\tau},\bm{b}_{V_{j}}=\bm{b}_{V_{j}}-\bm{b}_{i_{\tau},\tau},$
	$\displaystyle T_{V_{j},\tau}$	$\displaystyle=T_{V_{j},\tau}-T_{i_{\tau},\tau},C_{j,\tau}=C_{j,\tau}-\{i_{\tau}\},$
	$\displaystyle\bm{M}_{V_{j}^{\prime},\tau}$	$\displaystyle=\bm{M}_{i_{\tau},\tau},\bm{b}_{V_{j}^{\prime},\tau}=\bm{b}_{i_{\tau},\tau},$
	$\displaystyle T_{V_{j}^{\prime},\tau}$	$\displaystyle=T_{i_{\tau},\tau},C_{j^{\prime},\tau}=\{i_{\tau}\}$

Appendix

Algorithm 16 Split

\left\lVert\tilde{\bm{\theta}}_{j_{1}}-\tilde{\bm{\theta}}_{j_{2}}\right\rVert<\frac{\alpha_{1}}{2}(F(T_{V_{j_{1}}})+F(T_{V_{j_{2}}}))+\frac{\alpha_{2}}{2}\epsilon_{*}

Appendix

Algorithm 17 Merge

Panel of Figure 26 — Figure A.1 : The cumulative regret of the algorithms under different scales of misspecification level.

Panel of Figure 27 — Figure A.2 : Cumulative regret in different corruption levels

Panel of Figure 28 — Figure A.3 : Cumulative regret with different cluster numbers

	$\displaystyle\overline{\bm{\theta}}_{t}$	$\displaystyle=\arg\min_{\bm{\theta}}-\frac{1}{m}\sum_{s\in[t-1]\atop i_{s}\in\overline{C}_{t}}\left(y_{s}\log\mu\left(h(\bm{x}_{s,1};\bm{\theta})-h(\bm{x}_{s,2};\bm{\theta})\right)+(1-y_{s})\log\mu\left(h(\bm{x}_{s,2};\bm{\theta})-h(\bm{x}_{s,1};\bm{\theta})\right)\right)$
		$\displaystyle+\frac{\lambda}{2}\left\lVert\bm{\theta}-\bm{\theta}_{0}\right\rVert_{2}^{2};$		(A.298)

Appendix

Algorithm 19 Clustering Of Neural Dueling Bandits (CONDB)

Explore similar work

Jul 22, 2026cs.DS

Algorithmic Approaches to Sequential Decision-Making and Social Epistemology

As humans, we face many decisions that require us to choose between sticking to something and giving up. This thesis uses algorithmic tools to derive insights about such decision-making problems in theoretical models, studying both near-optimal methods and outcomes of social and behavioral influences. Along the way, this thesis sheds light on what we gain and what we lose as we move from a messy and complex real world setting to a very general abstract model by studying various points along this spectrum. In Part I, we study algorithms for sequential decision-making in the improving multi-armed bandits problem. We provide nearly matching upper and lower bounds in the general case. Then, we then ask what is possible if we have access to similar instances to the one we wish to deploy our algorithm on. To that end, we provide guarantees in the data-driven algorithm design framework, showing that a polynomial number of samples is sufficient for learning good algorithms from a class of algorithms. In Part II, we study algorithmic approaches for problems in social epistemology. We start by analyzing what role theoretical models can play in the study of social problems. We then study social and behavioral influences in decision-making requiring investment. First, we provide mathematical formalism in which to study the formation of pessimism traps, a phenomenon identified by philosophers in which agents are influenced by their predecessors to engage in less-ambitious goals. We develop financial interventions to sustainably shift communities out of these traps. The second problem we study is the influence of grit as a behavioral trait in ambitious decision-making. Overall, these works seek to theoretically model phenomena in social epistemology and provide a framework for intervening algorithmically.

Kavya Ravichandran

Toyota Technological Institute at Chicago, Chicago, IL · at the Toyota Technological Institute at Chicago Chicago, IL

Sequential Decision Making Algorithmic Cores Pessimism Epistemology

Ask PDF

Apr 28, 2026cs.LG

Online combinatorial optimization with stochastic decision sets and adversarial losses

Most work on sequential learning assumes a fixed set of actions that are available all the time. However, in practice, actions can consist of picking subsets of readings from sensors that may break from time to time, road segments that can be blocked or goods that are out of stock. In this paper we study learning algorithms that are able to deal with stochastic availability of such unreliable composite actions. We propose and analyze algorithms based on the Follow-The-Perturbed-Leader prediction method for several learning settings differing in the feedback provided to the learner. Our algorithms rely on a novel loss estimation technique that we call Counting Asleep Times. We deliver regret bounds for our algorithms for the previously studied full information and (semi-)bandit settings, as well as a natural middle point between the two that we call the restricted information setting. A special consequence of our results is a significant improvement of the best known performance guarantees achieved by an efficient algorithm for the sleeping bandit problem with stochastic availability. Finally, we evaluate our algorithms empirically and show their improvement over the known approaches.

Gergely Neu, Michal Valko

SequeL team, INRIA Lille – Nord Europe, France

Bandits Optimistic Follow-The-Regularized-Leader Combinatorial Optimization Adversarial Training

Ask PDF

Jul 20, 2026cs.AI

Reinforcement Learning: From Algorithms To Foundation Models

Reinforcement learning (RL) provides a framework for sequential decision making under explicit objectives. In its classical form, RL studies how an agent should act to maximise long-term reward in a dynamic environment. In richer settings, the problem extends beyond a single agent and fixed environment: intelligent behavior may require strategic interaction, adaptation to uncertainty, and reasoning over high-dimensional worlds. This thesis studies RL from two perspectives: algorithms in games and RL in the era of foundation models. The first part focuses on multi-agent RL in games. It examines how incentives, policies, and equilibrium concepts interact in competitive and general-sum environments, spanning two-player zero-sum games, large-scale video games, and multi-player settings with general structure. These works investigate learning in multi-agent systems and the behavior of RL methods in interactive environments. The second part studies RL with generative and foundation models, motivated by the idea that prior knowledge can enrich sequential decision making. Pretrained generative models and learned world models serve as representation tools and structured priors for planning, control, and policy optimization. The thesis develops diffusion-based world models, investigates RL for efficient video generation, explores generative models as policy classes, and studies interactive video world models in which actions shape future observations. It also addresses long-horizon modeling through architectures with memory. Together, these contributions present a unified view of RL as objective-driven adaptation in complex sequential domains. From strategic games to generative world models, the thesis highlights how RL connects decision making, environment modeling, and emerging foundation-model capabilities, offering a broader perspective on the principles underlying intelligent behavior.

Zihan Ding

Department of Electrical Computer Engineering, Princeton University

Multi-Agent Reinforcement Learning Video World Models Foundation Model Equilibrium

Ask PDF