Exploration-Exploitation

We study the active learning problem of fixed-confidence top-$k$ identification from noisy pairwise comparisons. In this problem, an algorithm sequentially chooses pairs of items to compare, observes the outcomes, and stops when it can return the set of top-$k$ items with error probability at most $\delta$. The objective is to design such a *$\delta$-correct* procedure that minimizes the expected number of comparisons (the sample complexity). This problem falls within the broader literature on fixed-confidence pure exploration in bandit models, where a common target is asymptotic optimality: the algorithm's expected sample complexity matches the information theoretic lower bound as $\delta \to 0$. Asymptotically optimal procedures have been developed for a range of fixed-confidence pure-exploration problems, however to the best of our knowledge, for top-$1$, or more generally top-$k$ identification from pairwise comparisons under latent utility models an asymptotically optimal algorithm has not been established. In this setting, we develop such an algorithm. We characterize the structure of the lower bound and formulate it as a saddle-point problem. This structure enables a computationally efficient primal--dual procedure that learns the asymptotically optimal comparison allocation online. We then construct an adaptive comparison-allocation algorithm that tracks the allocation learned by the primal--dual procedure and prove it is asymptotically optimal.

We study the decoupled multi-armed bandit problem, where the learner separately selects one arm for exploration and one, possibly different, arm for exploitation at each round. In this setting, the loss of the explored arm is observed but not incurred, whereas the loss of the exploited arm is incurred without being observed. We propose an efficient Follow-the-Perturbed-Leader (FTPL) policy that achieves Best-of-Both-Worlds (BOBW) guarantee with constant regret in the stochastic regime and optimal $\mathcal{O}(\sqrt{KT})$ regret in the adversarial regime. A key feature of our method is that it completely avoids both the convex optimization required by prior BOBW policies and the resampling procedures typically used in FTPL bandit policies. This allows FTPL to fully realize its computational efficiency advantages, leading to substantial reductions in computational cost. We empirically confirm that our policy not only improves the runtime but also demonstrates superior regret performance in both regimes.

Efficient exploration remains a key challenge in deep reinforcement learning, especially for embodied agents operating in realistic environments with high-dimensional observations and complex dynamics. Recent latent exploration methods define bonuses in a learned latent space, but often struggle in these settings where (i) representations can be noisy or policy-dependent, and (ii) common strategies such as randomized latent objectives or fixed directional spanning are brittle and fail to improve global coverage. We propose Covariance Volume Maximization (CVM), a coverage-driven latent exploration framework with two key components. First, we learn a behavioral state encoder using a *policy-mixture* objective to reduce representation drift under rapidly changing exploration policies, yielding stable and behaviorally meaningful latent displacements. Second, CVM rewards each transition by its exact increase in the log-determinant of the covariance of recent latent displacements, explicitly expanding the explored region and prioritizing under-covered directions. This objective coincides with the classical *D-optimal* design criterion, providing an information-efficiency justification. Extensive experiments on embodied navigation and manipulation tasks demonstrate that CVM substantially improves exploration efficiency and robustness, and scales effectively to different environments.

We present Creat3r, an iterative next-best-view (NBV) selection framework for efficient, high-quality 3D reconstruction. Starting from a small seed set of image-pose pairs, Creat3r repeatedly selects the most informative next camera pose. After each pose is chosen, the corresponding image is acquired and added to the multi-view set to update a 3DGS reconstruction. To guide selection, Creat3r constructs an intermediate point cloud and estimates reconstruction reliability via a novel 3D confidence field, which is projected to candidate poses through Gaussian projection to produce 2D confidence and exploration maps. These maps balance exploitation of reliable regions and exploration of uncertain or unseen areas under computational constraints. Experiments with standard 3DGS show that Creat3r consistently outperforms baselines in novel view synthesis and surface reconstruction, achieving higher SSIM and F1 scores with fewer views.

Recent advances in online reinforcement learning (RL) for large language models (LLMs) have demonstrated promising performance in complex reasoning tasks. However, they often exhibit an imbalanced exploration–exploitation trade-off, resulting in unstable optimization and sub-optimal performance. We introduce IB-Score, a novel metric grounded in Information Bottleneck (IB) theory that evaluates policy’s exploration-exploitation balance by quantifying the trade-off between step-level reasoning diversity and mutual information shared with the correct answer. Analysis based on IB-Score shows that popular online RL approaches (e.g., GRPO) with common regularization methods fail to consistently maintain balance during training with suboptimal results. To address this, we propose Information Bottleneck-driven Tree-based Policy Optimization (IB-TPO), a principled framework that formulates IB-Score as a fine-grained optimization objective and utilizes a novel IB-guided tree sampling strategy that not only improves the efficiency of online sampling with 50\% more trajectories under same token budget, but also reuses the tree structure for effective IB-Score Monte Carlo estimation. Extensive experiments across standard benchmarks show that our method significantly outperforms GRPO baseline by 2.9% to 3.6% and also outperforms other state-of-the-art online RL approaches.

We study *reward-free* and *reward-agnostic* exploration in episodic finite-horizon Markov decision processes (MDPs), where an agent explores an unknown environment without observing external rewards. Reward-free exploration aims to enable $\epsilon$-optimal policies for *any* reward revealed after exploration, while reward-agnostic exploration targets $\epsilon$-optimality for rewards drawn from a small finite class. In the *reward-agnostic setting*, Li, Yan, Chen, and Fan (2024) achieve minimax sample complexity, but only for restrictively small accuracy parameter $\epsilon$. We propose a new algorithm that significantly relaxes the requirement on $\epsilon$. Our approach is novel and of technical interest by itself. Our algorithm employs an online learning procedure with carefully designed rewards to construct an exploration policy, which is used to gather data sufficient for accurate dynamics estimation and subsequent computation of an $\epsilon$-optimal policy once the reward is revealed. Finally, we establish a tight lower bound for *reward-free exploration*, closing the gap between known upper and lower bounds.

Real-world reinforcement learning often faces environment drift, but most existing methods rely on static entropy coefficients/target entropy, causing over-exploration during stable periods and under-exploration after drift (thus slow recovery), and leaving unanswered the principled question of how exploration intensity should scale with drift magnitude. We show that, under standard assumptions, entropy scheduling in non-stationary maximum-entropy RL can be cast as the dynamic-regret trade-off between tracking a drifting comparator and stabilizing updates, yielding a square-root scaling rule for the entropy weight in terms of a (possibly conservative) online non-stationarity proxy. Building on this, we propose AES (Adaptive Entropy Scheduling), which adaptively adjusts the entropy coefficient/temperature online using observable drift proxies during training, requiring almost no structural changes and incurring minimal overhead. Across 4 algorithm variants, 12 tasks, and 4 drift modes, AES significantly reduces the fraction of performance degradation caused by drift and accelerates recovery after abrupt changes.

We study bilinear bandits with partially observable features on both the user and item sides. In each of $T$ rounds, the learner selects a user--item pair and observes only the reward for the chosen pair. The reward model is bilinear in the user and item features with an unknown parameter matrix. Existing work commonly reduces this problem to a linear bandit via Kronecker-product features, increasing dimensionality and losing bilinear structure. We propose \texttt{BiRoLF}, an algorithm robust to latent features, which directly leverages the bilinear structure without such linearization. It augments observed feature spaces on both sides with orthogonal complement bases and employs doubly robust (DR) estimation to impute rewards for unselected pairs, constructing matrix-valued pseudo-rewards. We estimate the effective parameter using a bilinear DR-Lasso estimator, which promotes sparsity in components orthogonal to observed features. \texttt{BiRoLF} achieves a $\tilde{O}(\sqrt{(d_x + d_{h_x})(d_y + d_{h_y}) T})$ regret bound, where $d_x$ and $d_y$ are observable feature dimensions, and $d_{h_x}$ and $d_{h_y}$ denote effective orthogonal-complement dimensions. By exploiting the induced block-diagonal Gram structure, \texttt{BiRoLF} performs an exact blockwise update that preserves the full DR-Lasso objective. Numerical experiments show strong regret performance and computational gains.

A natural recipe for intelligent robotic decision-making is initializing from pretrained generative control policies, which have summarized offline experience, and adapting them to self-collected online experience. We present DF-ExpEnse, an exploration technique that improves the quality of online experience collection, thus increasing finetuning sample-efficiency. DF-ExpEnse leverages the multimodal modeling capabilities of the generative control policy to create an expressive and tractably evaluatable candidate set. It then utilizes an ensemble of critics to identify the action that best balances quality with high exploration interest. In fleet settings, DF-ExpEnse further enables cross-agent communication to facilitate collaborative exploration as a group. DF-ExpEnse can be seamlessly integrated with existing strategies that finetune pretrained generative control policies via reinforcement learning. We experimentally validate consistent sample-efficiency benefits through DF-ExpEnse across a variety of manipulation and locomotion tasks, compared to default finetuning and alternative action selection schemes. Project can be found at [df-expense.github.io](https://df-expense.github.io).

Decentralized Federated Learning (DFL) enables collaborative model training across connected clients without a central server, effectively mitigating communication bottlenecks and avoiding the single point of failure in Centralized Federated Learning (CFL). However, existing DFL methods mostly focus on parameter averaging with compromised update directions, which limits their performance potential due to insufficient exploration of the loss landscape, especially for complex models. We observe that layer exchanges among clients enhance exploration while introducing instability due to highly diverse update directions. To address these limitations, we propose Decentralized Layer-wise Fusion (DecFus), the first DFL framework that unifies layer-level exchange and averaging to balance exploration and exploitation. DecFus dynamically transitions the decentralized training process from exploration-dominant to exploitation-dominant phases, guided by the loss variance among connected neighbors. Furthermore, a layer-wise fusion strategy, informed by pairwise cosine similarity, categorizes all layers into two groups: an exchange group for exploration and an averaging group for exploitation. Specifically, we theoretically establish the convergence of DecFus without relying on the common assumption in existing literature that the aggregation matrix must be doubly stochastic. Extensive experiments demonstrate that DecFus achieves superior performance in both IID and non-IID scenarios, substantially outperforming existing CFL and DFL methods.

Recommender systems play a crucial role in internet economies by connecting users with relevant products. However, designing effective recommender systems faces the key challenges: the exploration-exploitation tradeoff in securing incentive to explore new products against user’s self-interested preferences. While prior work addresses Bayesian Incentive Compatibility (BIC) in fixed-design linear bandits (Sellke & Slivkins, 2023), we tackle the challenge of stochastic user covariates sampled online. Unlike standard black-box reductions (Mansour et al., 2020), our two-stage framework exploits the linear reward structure to achieve sublinear regret while satisfying incentive constraints. To address it, we propose a two-stage algorithm that integrates incentivized exploration with any efficient plug-in offline learning algorithms. In the first stage, it explores products while maintaining incentive compatibility to gather optimal samples. The second stage employs inverse proportional gap sampling strategy (IPGS) integrated with any efficient learning methods to secure sublinear regret. Theoretically, we prove that algorithm RCB achieves $O(\sqrt{KdT})$ regret and simultaneously satisfies incentive constraints, and discovers the tradeoff between incentive budget and regret, validating in experiments. We demonstrate RCB’s strong incentive gain, sublinear regret, and robustness through a real application on personalized warfarin dosing and simulations.

In this paper, we address the standard $K$-armed multi-armed bandit (MAB) with heterogeneous data sources, each exhibiting unknown and distinct noise variances, $\lbrace \sigma_j^2 \rbrace_{j=1}^{M}$. The learner performs standard regret minimization, with the added challenge of choosing which data source to query at each round. We propose SOAR (Source-Optimistic Adaptive Regret minimization), a novel algorithm that adaptively balances exploration and exploitation by jointly constructing upper confidence bounds for arm rewards and lower confidence bounds for data source variances. Our theoretical analysis establishes that SOAR achieves a regret bound of $\tilde{O}\left({\sigma^\star}^2 \sum_{i=2}^K \tfrac{1}{\Delta_i}\right),$ along with a preprocessing cost that depends only on the problem parameters $\lbrace \sigma_j \rbrace_{j=1}^{M}$, $K$, and grows at most logarithmically with the horizon $T$; where ${\sigma^\star}^2$ is the minimum source variance, and $\Delta_i$ denotes the suboptimality-gap of the $i$-th arm reward. The $\tilde{O}(\cdot)$ notation hides the polylogarithmic factors in these problem parameters. Notably, despite not knowing the minimum-variance source, SOAR matches the instance-dependent regret of a standard MAB run on a single source of variance $\sigma^\star$. This near-optimal instance-dependent regret analysis of SOAR underscores its effectiveness in dynamically managing heteroscedastic noise without incurring significant overhead. Experiments on synthetic problem instances as well as a real dataset (MovieLens 32M) demonstrate that our method significantly outperforms baseline bandit algorithms in terms of regret performance. Our work opens a new direction for adaptively leveraging multiple heterogeneous data sources, extending beyond traditional bandit frameworks.

Traditional e-commerce search systems employ multi-stage cascading architectures that suffer from fragmented computation and optimization objective collisions across stages, ultimately limiting their performance ceiling. We propose \textbf{OneSearch}, the first industrial-deployed end-to-end generative framework for e-commerce search, featuring three key innovations: (1) Keyword-enhanced Hierarchical Quantization Encoding to preserve hierarchical semantics and distinctive item attributes while maintaining strong query-item relevance constraints; (2) multi-view user behavior sequence injection that constructs behavior-driven user IDs and incorporates both explicit short-term and implicit long-term sequences; and (3) a Preference-Aware Reward System with multi-stage supervised fine-tuning and adaptive reward-weighted ranking to capture fine-grained user preferences. Extensive offline evaluations demonstrate its superior performance, while online A/B tests achieve statistically significant improvements: +1.67\% item CTR, +2.40\% buyer, and +3.22\% order volume. OneSearch reduces operational expenditure by 75.40\%, improves Model FLOPs Utilization from 3.26\% to 27.32\%, and has been successfully deployed across multiple search scenarios in Kuaishou, serving millions of users daily. Code is in https://github.com/benchen4395/onesearch-family.

Scaling test-time compute with multi-path chain-of-thought can improve reasoning accuracy, but its gains hinge on an effective exploration–exploitation trade-off. Existing methods handle this trade-off in rigid ways: tree-structured search hard-codes exploration via brittle expansion rules that disrupt post-trained reasoning, while parallel reasoning over-explores redundant hypothesis paths and relies on a weak answer selection strategy. Driven by the insight that the optimal balance is *phase-dependent* and that correct vs. incorrect paths often *diverge only at late stages*, we reconceptualize test-time scaling as a dynamic *expand–reduce* control problem over a pool of hypothesis paths. We introduce **HyPER**, a *training-free online control policy* for MoE multi-path decoding that reallocates compute under a fixed budget using lightweight path statistics. HyPER features (i) an *online controller* that shifts from exploration to exploitation as the hypothesis pool evolves, (ii) an MoE-based token-level refinement primitive for efficient *generation-time exploitation* without full-path resampling, and (iii) a length- and confidence-aware aggregation rule to bridge the existence–selection gap for reliable *answer-time exploitation*. Extensive experimental results across four MoE models and diverse benchmarks demonstrate HyPER consistently achieves the accuracy–compute Pareto frontier, outperforming prior-art methods by 8-10% while reducing token consumption by 25-40%.

We study a stylized social learning dynamics where self-interested agents collectively follow a simple multi-armed bandit protocol. Each agent controls an "episode": a short sequence of consecutive decisions. Motivating applications include users repeatedly interacting with an AI, or repeatedly shopping at a marketplace. While agents are incentivized to explore within their respective episodes, we show that the aggregate exploration fails: e.g., its Bayesian regret grows linearly over time. In fact, such failure is a (very) typical case, not just a worst-case scenario. This conclusion persists even if an agent's per-episode utility is some fixed function of the per-round outcomes: e.g., $\min$ or $\max$, not just the sum. Thus, externally driven exploration is needed even when some amount of exploration happens organically.

Diffusion Language Models (DLMs) have recently emerged as a strong alternative to autoregressive language models (AR-LMs), due to their comparable accuracy and faster inference speed via parallel decoding. However, standard DLM decoding strategies, which rely on unmasking only high-confidence tokens, encounter an inherent information-theoretic bottleneck that restricts decoding progress and ultimately slows down generation. We demonstrate this through an information-theoretic lower bound that the number of decoding rounds must grow linearly with the sample's total information and inversely with the per-round information budget, establishing a bits-to-rounds principle. Motivated by this theory, we propose Explore-Then-Exploit (ETE), a training-free decoding strategy that maximizes information throughput and decoding efficiency. ETE combines cross-block decoding with targeted exploration of high-uncertainty tokens to reshape the conditional distribution and trigger cascades of confident predictions. Experiments across diverse benchmarks verify our theoretical bounds and demonstrate that ETE consistently reduces the number of decoding rounds compared to confidence-only baselines without compromising generation quality. Furthermore, ETE integrates efficiently with KV caching, translating these algorithmic gains into improved tokens-per-second throughput.

Users increasingly face the challenge of selecting an appropriate LLM for a given task from a rapidly growing pool of LLMs, each with distinct but often opaque latent properties. Compounding this challenge, users may lack the vocabulary or awareness to explicitly articulate the characteristics they value in an LLM's responses or deployment. We propose an interaction-efficient active learning framework in which a dueling bandit algorithm iteratively selects pairs of LLMs, collects user feedback about their responses, and updates its belief about the user's latent preferences. We introduce a novel belief-aware upper confidence bound strategy that balances exploration of the model pool with exploitation of inferred preferences, enabling efficient alignment between user needs and LLM capabilities under user-specified cost and time budgets. Through diverse experiments on LLMs and human studies, we experimentally verify that our model can efficiently match users to LLMs at a lower cost.

We address the problem of multi-group mean estimation, which seeks to allocate a finite sampling budget across multiple groups to obtain uniformly accurate estimates of their means. Unlike classical multi-armed bandits, whose objective is to minimize regret by identifying and exploiting the best arm, the optimal allocation in this setting requires sampling every group on the order of $\Theta(T)$ times. This fundamental distinction makes exploration-free algorithms both natural and effective. Our work makes three contributions. First, we strengthen the existing results on subgaussian variance concentration using the Hanson-Wright inequality and identify a class of strictly subgaussian distributions that yield sharper guarantees. Second, we design exploration-free non-adaptive and adaptive algorithms, and we establish tighter regret bounds than the existing results. Third, we extend the framework to contextual bandit settings, an underexplored direction, and propose algorithms that leverage side information with provable guarantees. Overall, these results position exploration-free allocation as a principled and efficient approach to multi-group mean estimation, with potential applications in experimental design, personalization, and other domains requiring accurate multi-group inference.

Reinforcement learning algorithms such as GRPO have driven recent advances in large language model (LLM) reasoning. While scaling the number of rollouts stabilizes training, existing approaches suffer from limited exploration on challenging prompts and leave informative feedback signals underexploited, due to context-independent rollout allocation across prompts (e.g., generating 16 rollouts per prompt) and relying heavily on sparse rewards. This paper presents XRPO (eXplore–eXploit GRPO), a unified framework that recasts policy optimization through the principled lens of rollout exploration–exploitation. To enhance exploration, XRPO introduces a mathematically grounded rollout allocator that adaptively prioritizes prompts with higher potential for uncertainty reduction. It further addresses stagnation on zero-reward prompts through an in-context seeding strategy that injects curated exemplars, steering the model into more difficult reasoning trajectories. To strengthen exploitation, XRPO develops a group-relative, novelty-aware advantage sharpening mechanism that leverages sequence likelihoods to amplify low-probability yet correct responses, thereby extending the policy’s reach beyond sparse rewards. Experiments across diverse math and coding benchmarks on both reasoning and non-reasoning models demonstrate that XRPO outperforms existing advances (e.g., GRPO and GSPO) up to 4% pass@1 and 6% cons@32, while accelerating training convergence by up to 2.7x.