Abstract:

We study model-based reinforcement learning with non-linear function approximation where the transition function of the underlying Markov decision process (MDP) is given by a multinomial logistic (MNL) model, and we consider the infinite-horizon average reward setting. Our first algorithm $UCRL2-MNL$ applies to the class of communicating MDPs and achieves an $\tilde{O}(dD\sqrt{T})$ regret, where $d$ is the dimension of feature mapping, $D$ is the diameter of the underlying MDP, and $T$ is the horizon. The second algorithm $OVIFH-MNL$ is computationally more efficient and applies to the more general class of weakly communicating MDPs, for which we show a regret guarantee of $\tilde{O}(d^{2/5} \mathrm{sp}(v^*)T^{4/5})$ where $\mathrm{sp}(v^*)$ is the span of the associated optimal bias function. We also prove a lower bound of $\Omega(d\sqrt{DT})$ for learning communicating MDPs with diameter at most $D$. Furthermore, we show a regret lower bound of $\Omega(dH^{3/2}\sqrt{K})$ for learning $H$-horizon episodic MDPs with MNL function approximation where $K$ is the number of episodes, which improves upon the best-known lower bound for the finite-horizon setting. This is based on joint work with Jaehyun Park (KAIST ISysE).

Abstract:

We propose an approximate Thompson sampling algorithm that learns linear quadratic regulators (LQR) with an improved Bayesian regret bound of $O(\sqrt{T})$. Our method leverages Langevin dynamics with a meticulously designed preconditioner as well as a simple excitation mechanism. We show that the excitation signal induces the minimum eigenvalue of the preconditioner to grow over time, thereby accelerating the approximate posterior sampling process. Moreover, we identify nontrivial concentration properties of the approximate posteriors generated by our algorithm. These properties enable us to bound the moments of the system state and attain an $O(\sqrt{T})$ regret bound without the unrealistic restrictive assumptions on parameter sets that are often used in the literature.
This is joint work with Gihun Kim (SNU ECE) and Insoon Yang (SNU ECE), and is based on the recent preprint of the same title.

Abstract:

Adapting to a priori unknown noise level is a very important but challenging problem in sequential decision-making as efficient exploration typically requires knowledge of the noise level, which is often loosely specified. We report significant progress in addressing this issue in linear bandits in two respects. First, we propose a novel confidence set that is `semi-adaptive' to the unknown sub-Gaussian parameter $\sigma^2_*$ where the confidence width w.r.t. the dimension d scales with $\sigma^2_*$ rather than the specified sub-Gaussian parameter $\sigma^2_0$ that can be much larger than $\sigma^2_*$. In particular, when the true noise level is zero, this leads to removing a factor of $\sqrt{d}$ from the confidence width and the regret bound when used for linear bandits. Second, for bounded rewards, we propose a novel variance-adaptive confidence set that has a much improved numerical performance upon prior art while removing unrealistic assumptions. We then apply this confidence set to develop, as we claim, the first practical variance-adaptive linear bandit algorithm via an optimistic approach, which is enabled by our novel regret analysis technique. Both of our confidence sets rely critically on `regret equality' from online learning. Our empirical evaluation in Bayesian optimization tasks shows that our algorithms demonstrate better or comparable performance compared to existing methods.
This is joint work with Jungtaek Kim (Univ. of Pittsburg) and is based on the recently accepted ICML 2024 paper of the same title.

Abstract:

Learning from Human Feedback has recently garnered considerable interest, especially with the advent of ChatGPT, which aligns with human preferences through Reinforcement Learning from Human Feedback (RLHF). In the context of the Bradley-Terry model, feedback is modeled as a logistic bandit problem, a common approach for capturing user preferences, such as click versus no-click in advertisement recommendation systems. Previous research often neglects dependencies in $S$, the norm of the unknown parameter vector, which becomes a significant issue when $S$ is large. We first introduce Regret-to-Confidence Set Conversion (R2CS), which constructs a convex, Likelihood Ratio-based Confidence Set solely based on the existence of an online learning algorithm with a regret guarantee. The novel confidence sets result in the optimal regret for the logistic bandits.
This is joint work with Junghyun Lee (KAIST AI) and Kwang-Sung Jun (Univ. of Arizona CS), and is based on the following two papers:

• Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion (AISTATS 2024)
• A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits (forthcoming, oral at ICML 2024 ARLET Workshop)

Abstract:

We study a stochastic sparse linear bandit problem where only a sparse subset of context features affects the expected reward function, i.e., the unknown reward parameter has sparse structure. In the existing Lasso bandit literature, the compatibility conditions together with additional diversity conditions on the context features are imposed to achieve regret bounds that only depend logarithmically on the ambient dimension $d$. In this paper, we demonstrate that even without the additional diversity assumptions, the compatibility condition only on the optimal arm is sufficient to derive a regret bound that depends logarithmically on $d$, and our assumption is strictly weaker than those used in the lasso bandit literature under the single parameter setting. To our knowledge, the proposed algorithm requires the weakest assumptions among Lasso bandit algorithms under a single parameter setting that achieve $O(\mathrm{poly} \log dT)$ regret. This is a joint work with Harin Lee and Taehyun Hwang from SNU and is based on the recent preprint of the same title.

Abstract:

In this presentation, we will explore significant advancements in multi-armed bandits with heavy-tailed rewards. The first paper, "Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy-Tailed Rewards (NeurIPS 2020)," proposes an adaptive perturbation method combined with a p-robust estimator, offering both theoretical and empirical improvements over existing methods. The second paper, "Minimax Optimal Bandits for Heavy-Tail Rewards (TNNLS 2024)," introduces a robust estimator and a perturbation-based exploration strategy that achieve minimax optimal regret bounds without prior knowledge of reward distribution bounds. Recently, I extended these approaches to distributional settings, further enhancing their applicability and performance.