Non-stationary multi-armed bandit (MAB) problems have recently attracted extensive attention. We focus on the abruptly changing scenario where reward distributions remain constant for a certain period and change at unknown time steps. Although Thompson sampling (TS) has shown success in non-stationary settings, there is currently no regret bound analysis for TS with uninformative priors. To address this, we propose two algorithms, discounted TS and sliding-window TS, designed for sub-Gaussian reward distributions. For these algorithms, we establish an upper bound for the expected regret by bounding the expected number of times a suboptimal arm is played. We show that the regret upper bounds of both algorithms are , where T is the time horizon and is the number of breakpoints. This upper bound matches the lower bound for abruptly changing problems up to a logarithmic factor. Empirical comparisons with other non-stationary bandit algorithms highlight the competitive performance of our proposed methods.
13 August 2025 in IEEE Transactions on Information Theory
We study the problem of reinforcement learning from human feedback (RLHF), a critical problem in training large language models, from a theoretical perspective. Our main contribution is the design of novel sample-efficient RLHF algorithms based on information-directed sampling (IDS), an online decision-making principle inspired by information theory. Our algorithms maximize the sum of the value function and a mutual information term that encourages exploration of the unknown environment (which quantifies the information gained about the environment through observed human feedback data). To tackle the challenge of large state spaces and improve sample efficiency, we construct a simplified surrogate environment and introduce a novel distance measure (named the $\ell _{g}$ -distance), enabling our IDS-based algorithm to achieve a Bayesian regret upper bound of order $O(H^{3/2}\sqrt {\log (K(\epsilon)) T})$ , where H is the episode length, T is the number of episode and $K(\epsilon)$ is related to the covering number of the environment. Specializing to the tabular settings, this regret bound is of order $\tilde {O}(H^{2}\sqrt {SAT})$ , where S and A are the numbers of states and actions. Finally, we propose an Approximate-IDS algorithm that is computationally more efficient while maintaining nearly the same sample efficiency. The design principle of this approximate algorithm is not only effective in RLHF settings but also applicable to the standard RL framework. Moreover, our work showcases the value of information theory in reinforcement learning and in the training of large language models.
Traditional few-shot action recognition (FSAR) aims to address the problem of the scarcity of action videos, enabling the recognition of action categories with just a few labeled samples. It is generally believed that the samples in the meta-training phase and the meta-testing phase are all drawn from the same domain. However, in practical applications, they often come from different domains, which may lead to significant differences in the distribution of spatiotemporal features. Researchers have started to study the problem of cross-domain few-shot action recognition (CDFSAR). The current solution is to train the model by combining source domain video and unlabeled target domain video to improve the model’s generalization ability. In this paper, we follow this paradigm but make a more refined use of the unlabeled target domain videos to better extract transferable features. First, we decouple the source and target domain videos along the temporal dimension and extract the domain-irrelevant features in both the source and target domains. Second, in each episode, we calculate the centroid of the domain-irrelevant features of the target domain and perform a momentum update on this feature centroid. We use Cross-Attention to align the domain-irrelevant features of the source domain toward this dynamic centroid. Finally, we use these aligned source domain features for few-shot classification. Experimental results demonstrate that our approach significantly improves few-shot classification performance across diverse domain shifts, validating the effectiveness of our refined use of unlabeled target video. Our code has been published at the URL: https://github.com/cofly2014/MCA-TRD.git.
Non-stationary multi-armed bandit (NS-MAB) problems have recently received significant attention. NS-MAB are typically modelled in two scenarios: abruptly changing, where reward distributions remain constant for a certain period and change at unknown time steps, and smoothly changing, where reward distributions evolve smoothly based on unknown dynamics. In this paper, we propose Discounted Thompson Sampling (DS-TS) with Gaussian priors to address both non-stationary settings. Our algorithm passively adapts to changes by incorporating a discounted factor into Thompson Sampling. DS-TS method has been experimentally validated, but analysis of the regret upper bound is currently lacking. Under mild assumptions, we show that DS-TS with Gaussian priors can achieve nearly optimal regret bound on the order of $\tilde{O}(\sqrt{TB_T})$ for abruptly changing and $\tilde{O}(T^β)$ for smoothly changing, where $T$ is the number of time steps, $B_T$ is the number of breakpoints, $β$ is associated with the smoothly changing environment and $\tilde{O}$ hides the parameters independent of $T$ as well as logarithmic terms. Furthermore, empirical comparisons between DS-TS and other non-stationary bandit algorithms demonstrate its competitive performance. Specifically, when prior knowledge of the maximum expected reward is available, DS-TS has the potential to outperform state-of-the-art algorithms.
Recently, few-shot action recognition has significantly progressed by learning the feature discriminability and designing suitable comparison methods. Still, there are the following restrictions. (a) Previous works are mainly based on visual mono-modal. Although some multi-modal works use labels as supplementary to construct prototypes of support videos, they can not use this information for query videos. The labels are not used efficiently. (b) Most of the works ignore the motion feature of video, although the motion features are essential for distinguishing. We proposed a Consistency Prototype and Motion Compensation Network(CLIP-CP$M^2$C) to address these issues. Firstly, we use the CLIP for multi-modal few-shot action recognition with the text-image comparison for domain adaption. Secondly, in order to make the amount of information between the prototype and the query more similar, we propose a novel method to compensate for the text(prompt) information of query videos when text(prompt) does not exist, which depends on a Consistency Loss. Thirdly, we use the differential features of the adjacent frames in two directions as the motion features, which explicitly embeds the network with motion dynamics. We also apply the Consistency Loss to the motion features. Extensive experiments on standard benchmark datasets demonstrate that the proposed method can compete with state-of-the-art results. Our code is available at the URL: https://github.com/xxx/xxx.git.