The Exploration-Exploitation tradeoff arises in Reinforcement Learning when one cannot tell if a policy is optimal. Then, there is a constant need to explore new actions instead of exploiting past experience. In practice, it is common to resolve the tradeoff by using a fixed exploration mechanism, such as -greedy ex…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “exploration exploitation tradeoff”
In this paper, we propose and study opportunistic bandits - a new variant of bandits where the regret of pulling a suboptimal arm varies under different environmental conditions, such as network load or produce price. When the load/price is low, so is the cost/regret of pulling a suboptimal arm (e.g., trying a suboptim…
Sparse reward is one of the biggest challenges in reinforcement learning (RL). In this paper, we propose a novel method called Generative Exploration and Exploitation (GENE) to overcome sparse reward. GENE automatically generates start states to encourage the agent to explore the environment and to exploit received rew…
Improved UCB method for stochastic bandits using distance tuning.
problem Improving performance in stochastic bandit problems.
method Tuning confidence bounds based on bandit distance.
result Empirically shows increased performance compared to existing methods.
Reinforcement learning studies how to balance exploration and exploitation in real-world systems, optimizing interactions with the world while simultaneously learning how the world operates. One general class of algorithms for such learning is the multi-armed bandit setting. Randomized probability matching, based upon …
Can one parallelize complex exploration exploitation tradeoffs? As an example, consider the problem of optimal high-throughput experimental design, where we wish to sequentially design batches of experiments in order to simultaneously learn a surrogate function mapping stimulus to response and identify the maximum of t…
Algorithm balances online and offline data for linear bandits.
problem Online learning with an offline dataset in linear bandits.
method Proposes a linear bandit algorithm that uses offline data early and increasingly favors exploration as the horizon grows.
result Establishes regret bounds showing competitive performance with both purely online and offline solutions.
Study explores strategies for randomized allocation in delayed rewards bandits.
problem Understanding the exploration-exploitation tradeoff in randomized strategies with delayed rewards.
method Examines two strategies: updating exploration sequence at every time point vs. updating only when a new reward is observed.
result The strategy updating only when a new reward is observed leads to strong consistency in allocation for a wider scope of situations.
Two-stage mechanism designs reduce regret in recommender systems with stochastic covariates.
problem Designing effective recommender systems with user covariates sampled online.
method Two-stage algorithm integrating incentivized exploration with offline learning methods.
result Achieves sublinear regret while maintaining incentive compatibility.
An online labor platform faces an online learning problem in matching workers with jobs and using the performance on these jobs to create better future matches. This learning problem is complicated by the rise of complex tasks on these platforms, such as web development and product design, that require a team of worker…
This paper extends the MAB problem to consider risk-reward tradeoffs.
problem Maximizing reward while accounting for risk in multi-armed bandit problems.
method Introduced the Risk Aware Lower Confidence Bound (RALCB) algorithm to solve the mean-variance MAB problem.
result The RALCB algorithm performs better than the algorithm in Sani et al. (2012) in both independent and dependent scenarios.
Efficient algorithm for CMDPs reduces to offline density estimation.
problem Offline learning for CMDPs with horizon H.
method Reduction to offline density estimation, layerwise exploration-exploitation tradeoff.
result First efficient and near-optimal reduction from CMDPs to offline density estimation.
New algorithm improves graph-based active learning by identifying unexplored regions.
problem Improving graph-based active learning by identifying unexplored regions.
method Poisson Reweighted Laplacian Uncertainty Sampling (PWLL) with a diagonal perturbation.
result PWLL effectively identifies unexplored regions in graph-based data.
Proper balance between exploitation and exploration is what makes good decisions, which achieve high rewards like payoff or evolutionary fitness. The Infomax principle postulates that maximization of information directs the function of diverse systems, from living systems to artificial neural networks. While specific a…
Proposes EE-Net for neural exploration in contextual bandits.
problem Exploitation-Exploration tradeoff in contextual bandits.
method Uses two neural networks: Exploitation and Exploration, to learn reward function and adaptively explore.
result Achieves regret and outperforms existing methods.
Monte Carlo Tree Search (MCTS) algorithms have achieved great success on many challenging benchmarks (e.g., Computer Go). However, they generally require a large number of rollouts, making their applications costly. Furthermore, it is also extremely challenging to parallelize MCTS due to its inherent sequential nature:…
ERTS uses Thompson sampling for Gaussian entropic risk bandits, achieving regret bounds.
problem Risk in decision making complicates reward maximization in MAB problems.
method ERTS (Entropic Risk Thompson Sampling) using Thompson sampling with an entropic risk measure.
result Regret bounds for ERTS under entropic risk measure provided.
The contextual bandit literature has traditionally focused on algorithms that address the exploration-exploitation tradeoff. In particular, greedy algorithms that exploit current estimates without any exploration may be sub-optimal in general. However, exploration-free greedy algorithms are desirable in practical setti…
We study the explore-exploit tradeoff in distributed cooperative decision-making using the context of the multiarmed bandit (MAB) problem. For the distributed cooperative MAB problem, we design the cooperative UCB algorithm that comprises two interleaved distributed processes: (i) running consensus algorithms for estim…
The purpose of this paper is to provide further understanding into the structure of the sequential allocation ("stochastic multi-armed bandit", or MAB) problem by establishing probability one finite horizon bounds and convergence rates for the sample (or "pseudo") regret associated with two simple classes of allocation…
Paper solves nonparametric contextual bandit with unbounded contexts.
problem Sequential decision making with unbounded context distributions.
method Two nearest neighbor methods combined with UCB exploration.
result Achieves minimax optimal regret under weak margin condition and light-tailed distributions.
SOO uses bandit theory to optimize functions with limited evaluations.
problem Optimizing functions with a limited number of evaluations.
method SOO is a machine learning approach that uses domain partitioning and a tradeoff between exploration and exploitation.
result SOO provides guarantees on the returned solution and is numerically efficient.
PC-PG balances exploration and exploitation in reinforcement learning.
problem Local policy gradient methods struggle with exploration.
method PC-PG uses an ensemble of learned policies (policy cover) to balance exploration and exploitation.
result PC-PG provides strong theoretical guarantees and empirical validation.
We consider the problem of selecting a seed set to maximize the expected number of influenced nodes in the social network, referred to as the \textit{influence maximization} (IM) problem. We assume that the topology of the social network is prescribed while the influence probabilities among edges are unknown. In order …
We approach the continuous-time mean-variance (MV) portfolio selection with reinforcement learning (RL). The problem is to achieve the best tradeoff between exploration and exploitation, and is formulated as an entropy-regularized, relaxed stochastic control problem. We prove that the optimal feedback policy for this p…
A new algorithm balances exploration and exploitation in online decision-making.
problem Balancing exploration and exploitation in online decision-making.
method Proposed -UCB algorithm incorporating conservative mechanism.
result Proved n-step upper regret bound for two situations.
Paper proposes CVaR-TS for risk-constrained MAB problems.
problem Risk in decision-making complicates reward maximization in MAB problems.
method Risk measure CVaR is used, and Thompson Sampling is adapted for CVaR.
result CVaR-TS outperforms other L/UCB-based algorithms in risk-constrained MAB settings.
Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selectionstat.ML
A new method for sparse linear bandits reduces exploration-exploitation tradeoff.
problem Sparse linear bandits in high-dimensional settings with finite actions.
method Best subset selection for parameter estimation and doubly growing epochs for regret minimization.
result Achieves nearly dimension-independent regret of with high probability.
LaMBO optimizes biological sequences using autoencoders and Bayesian optimization.
problem Bayesian optimization for drug design is limited by discrete, high-dimensional decision variables.
method Jointly trains denoising autoencoder with a Gaussian process head for gradient-based optimization in latent space.
result LaMBO outperforms genetic optimizers and requires no large pretraining corpus.
We integrate information-theoretic concepts into the design and analysis of optimistic algorithms and Thompson sampling. By making a connection between information-theoretic quantities and confidence bounds, we obtain results that relate the per-period performance of the agent with its information gain about the enviro…
We introduce the bilinear bandit problem with low-rank structure in which an action takes the form of a pair of arms from two different entity types, and the reward is a bilinear function of the known feature vectors of the arms. The unknown in the problem is a by matrix that defines the reward…
We study a budgeted hyper-parameter tuning problem, where we optimize the tuning result under a hard resource constraint. We propose to solve it as a sequential decision making problem, such that we can use the partial training progress of configurations to dynamically allocate the remaining budget. Our algorithm combi…
We consider the task of opportunistic channel access in a primary system composed of independent Gilbert-Elliot channels where the secondary (or opportunistic) user does not dispose of a priori information regarding the statistical characteristics of the system. It is shown that this problem may be cast into the framew…
We investigate a novel cluster-of-bandit algorithm CAB for collaborative recommendation tasks that implements the underlying feedback sharing mechanism by estimating the neighborhood of users in a context-dependent manner. CAB makes sharp departures from the state of the art by incorporating collaborative effects into …
New algorithms prove self-play can be effective in competitive RL.
problem Proving self-play algorithms' effectiveness in competitive reinforcement learning.
method Introduced Value Iteration with Upper/Lower Confidence Bound (VI-ULCB) and explore-then-exploit algorithms.
result Achieved regret bounds of and .
New algorithm reduces regret in sequential decision-making problems.
problem Balancing exploration and exploitation in online sequential decision problems.
method Variational Bayesian optimistic sampling (VBOS) for optimizing policies.
result VBOS achieves Bayesian regret for stochastic multi-armed bandits.
Algorithm balances learning and coverage for multi-robots over unknown fields.
problem Balancing learning and coverage for multi-robots over unknown, nonuniform sensory fields.
method DSLC algorithm that schedules learning and coverage epochs, using Gaussian Process modeling and coverage regret analysis.
result Upper bound on expected cumulative coverage regret provided for DSLC.
On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spacescs.LG
New RL algorithm tackles large state spaces using optimistic function approximation.
problem Challenges in reinforcement learning with large state spaces and modern function approximators.
method Optimistic modification of least-squares value iteration algorithm for kernel functions or overparameterized neural networks.
result Polynomial runtime and sample complexity, independent of the number of states, with regret.
Task offloading is an emerging technology in fog-enabled networks. It allows users to transmit tasks to neighbor fog nodes so as to utilize the computing resources of the networks. In this paper, we investigate a stochastic task offloading model and propose a multi-armed bandit framework to formulate this model. We con…
Recently, there has been rising interest in Bayesian optimization -- the optimization of an unknown function with assumptions usually expressed by a Gaussian Process (GP) prior. We study an optimization strategy that directly uses an estimate of the argmax of the function. This strategy offers both practical and theore…
Cellular network configuration plays a critical role in network performance. In current practice, network configuration depends heavily on field experience of engineers and often remains static for a long period of time. This practice is far from optimal. To address this limitation, online-learning-based approaches hav…
The enactive approach to cognition is typically proposed as a viable alternative to traditional cognitive science. Enactive cognition displaces the explanatory focus from the internal representations of the agent to the direct sensorimotor interaction with its environment. In this paper, we investigate enactive learnin…
Ensemble++ uses shared-factor ensembles to scale Thompson Sampling for linear and nonlinear bandits.
problem Computational challenges in Thompson Sampling for large-scale or non-conjugate settings.
method Ensemble++ with shared-factor architecture and random linear combinations.
result Ensemble++ achieves comparable regret to exact Thompson Sampling with significantly smaller ensemble sizes.
The paper explores robustness in linear regression models under adversarial attacks.
problem The impact of test-time adversarial attacks on linear regression models.
method Quantitative estimates and phase transitions analysis.
result Precise characterization of tradeoffs between adversarial robustness and accuracy.
New algorithm optimizes online decision-making with dynamically generated actions.
problem Balancing action generation costs with optimal decision-making in online learning.
method Doubly-optimistic algorithm using LCB for action selection and UCB for action generation.
result Achieves optimal regret bound of .
New meta-RL method avoids exploration-exploitation trade-off.
problem Learning to explore and exploit simultaneously in meta-RL.
method Developed new objectives for exploration and exploitation.
result DREAM outperforms existing methods on complex tasks.
We consider the exploration-exploitation tradeoff in linear quadratic (LQ) control problems, where the state dynamics is linear and the cost function is quadratic in states and controls. We analyze the regret of Thompson sampling (TS) (a.k.a. posterior-sampling for reinforcement learning) in the frequentist setting, i.…
Paper explores tradeoff between standard and robust accuracy for latent models.
problem Tradeoff between standard accuracy and robust accuracy in adversarial training.
method Revisits adversarial training for latent models, considering Gaussian mixture and generalized linear models.
result Low-dimensional manifold structure mitigates the tradeoff between standard and robust accuracy.