Optimizing rewards under budget constraints with correlated costs and rewards.
problem Maximizing total expected reward under a budget constraint on total cost with correlated and potentially heavy-tailed cost-reward pairs.
method Proposes algorithms exploiting correlation between cost and reward via linear minimum mean-square error estimation to achieve tight regret bounds.
result Achieves O ( log B ) O(\log B) O ( log B ) regret for a budget B > 0 B>0 B > 0 under certain moment conditions. Unified approach to correlated multi-armed bandits reduces regret significantly.
problem Correlated rewards in multi-armed bandits.
method Developed a unified approach to leverage reward correlations and presented algorithms with rigorous analysis.
result C-UCB algorithm pulls non-competitive arms only O(1) times, improving over classic algorithms.
Improved best-arm identification in correlated multi-armed bandits.
problem Best-arm identification in multi-armed bandits with correlated rewards.
method Proposed C-LUCB algorithm that exploits upper bounds on conditional rewards.
result Significant reduction in sample complexity for best-arm identification.
New method uses correlated auxiliary feedback to reduce regret in parameterized bandits.
problem Reducing regret in parameterized bandits with correlated auxiliary feedback.
method Develops a reward estimator using auxiliary feedback with tight confidence bounds.
result Shows significant reduction in regret compared to standard methods.
Mitigates biases in reward models using variational inference.
problem Spurious correlations in reward models that align large language models with human preferences.
method Formulates data-generating process, identifies non-spurious latent variables, and uses variational inference to recover them.
result Effective mitigation of spurious correlation issues, yielding more robust reward models.
A major challenge in reinforcement learning is exploration, when local dithering methods such as epsilon-greedy sampling are insufficient to solve a given task. Many recent methods have proposed to intrinsically motivate an agent to seek novel states, driving the agent to discover improved reward. However, while state-…
Resolves spurious correlations in causal models via intervention design.
problem Spurious correlations lead to incorrect causal models in reinforcement learning environments.
method Proposes a method to design interventions that improve causal models by incentivizing agents to find errors.
result Experimental results show improved causal models compared to baselines.
The paper tackles statistical and computational challenges in learning correlated reward models.
problem The Independence of Irrelevant Alternatives (IIA) assumption collapses human preferences into a universal utility function, leading to coarse approximations.
method The paper investigates the statistical and computational challenges of learning a correlated probit model using best-of-three preference data.
result Best-of-three preference data overcomes the limitations of pairwise preference data, allowing for more fine-grained modeling of human preferences.
A new algorithm for bandits with hierarchical rewards.
problem Learning from correlated rewards in complex hierarchies.
method Hierarchical Thompson Sampling (HierTS) for Gaussian hierarchies.
result Hierarchical Thompson Sampling reduces regret by non-constant factors in the number of actions.
PROBE optimizes best-arm identification with cheap proxies, improving sample complexity.
problem Fixed-confidence best-arm identification with costly rewards and correlated cheap proxies.
method PROBE uses control-variate adjustment and phase elimination to learn residual variance online.
result PROBE achieves oracle sample complexity up to a constant factor and additive calibration cost.
DART optimizes subset selection in non-linear bandit problems.
problem Optimizing subset selection in non-linear bandit problems with correlated rewards.
method DART algorithm for combinatorial bandits without individual arm feedback or linearity assumption.
result DART achieves a regret bound of i l d e O ( K K N T ) ilde{\mathcal{O}}(K\sqrt{KNT}) i l d e O ( K K N T ) . We consider the correlated multiarmed bandit (MAB) problem in which the rewards associated with each arm are modeled by a multivariate Gaussian random variable, and we investigate the influence of the assumptions in the Bayesian prior on the performance of the upper credible limit (UCL) algorithm and a new correlated U…
Reinforcement Learning (RL) agents require the specification of a reward signal for learning behaviours. However, introduction of corrupt or stochastic rewards can yield high variance in learning. Such corruption may be a direct result of goal misspecification, randomness in the reward signal, or correlation of the rew…
In this paper we consider the problem of online stochastic optimization of a locally smooth function under bandit feedback. We introduce the high-confidence tree (HCT) algorithm, a novel any-time X \mathcal{X} X -armed bandit algorithm, and derive regret bounds matching the performance of existing state-of-the-art in term…
A new algorithm reduces suboptimal arm selection in correlated bandits.
problem Structured bandits with correlated rewards.
method Confidence-based phased algorithm.
result Regret is uniformly bounded in certain structures.
The study categorizes reward errors in reinforcement learning, finding some can be beneficial.
problem Training language models with imperfect proxy rewards.
method Theoretical analysis of policy gradient optimization and categorization of reward errors.
result Reward errors can be benign or even beneficial, preventing policy from stalling.
The paper explores how mining costs, rewards, and blockchain security are interconnected.
problem Understanding the interdependencies between mining costs, mining rewards, and blockchain security.
method Theoretical derivation and empirical analysis using daily crypto market data and autoregressive distributed lag approach.
result Cryptocurrency price and mining rewards are intrinsically linked to blockchain security outcomes.
Automatically generates curricula for reinforcement learning agents.
problem Learning in dynamic, sparse reward environments.
method Setter-solver paradigm focusing on goal validity, feasibility, and coverage.
result Demonstrated success in 2D and 3D environments with varying goals.
Overfitting occurs when RL agents correlate rewards with spurious observation features.
problem Overfitting in reinforcement learning due to correlation with spurious observation features.
method Developed a framework to analyze and design synthetic benchmarks from modified observation spaces.
result Agents can overfit to different observation spaces even if the MDP dynamics are fixed.
Reinforcement learning agents are prone to undesired behaviors due to reward mis-specification. Finding a set of reward functions to properly guide agent behaviors is particularly challenging in multi-agent scenarios. Inverse reinforcement learning provides a framework to automatically acquire suitable reward functions…
New algorithms ensure fair selection in combinatorial semi-bandit with unrestricted delays.
problem Fair selection in stochastic combinatorial semi-bandit with delayed feedback.
method Introduced merit-based fairness constraints and new bandit algorithms for reward and fairness.
result Achieved sublinear expected reward and fairness regrets with dependence on delay distribution quantiles.
We consider the problem of learning to play a repeated multi-agent game with an unknown reward function. Single player online learning algorithms attain strong regret bounds when provided with full information feedback, which unfortunately is unavailable in many real-world scenarios. Bandit feedback alone, i.e., observ…
This work improves wireless network learning by using side-information about interference.
problem Improving online learning algorithms in wireless networks.
method Exploiting side-information like interference levels to improve learning algorithms.
result Improved learning algorithms achieve higher throughput with fewer samples.
Sparse rewards with different magnitudes speed up learning in model-based reinforcement learning.
problem Speeding up learning in model-based reinforcement learning methods.
method Add uniformly sampled reward values to sparse binary rewards during training.
result Training can be more efficient and faster with less variability.
Models analyze strategic risk-taking in continuous action games.
problem Strategic risk-taking dynamics in continuous action games.
method Normal form game, multi-player scenarios, regret minimization algorithms, numerical algorithm for calculation.
result Nash equilibrium also serves as a correlated equilibrium in continuous games.
Improved control approach for correlated bandits with better performance.
problem General multi-armed bandit problem with correlated elements.
method Introducing entropy regularisation to obtain a smooth asymptotic approximation of the value function, leading to a semi-index approximation of the optimal decision process.
result Performance of Asymptotic Randomised Control (ARC) algorithm compares favorably with other approaches.
New algorithm tackles nonstationary linear bandits with latent dynamics.
problem Nonstationary bandit problem with latent states and unknown dynamics.
method Explore-then-commit algorithm with exploration and commitment phases.
result Achieves i l d e O ( T 2 / 3 ) ilde{\mathcal{O}}(T^{2/3}) i l d e O ( T 2/3 ) regret. New algorithm uses machine learning to predict rewards for decision-making problems.
problem Sequential decision-making under uncertainty with scarce online data.
method Machine Learning-Assisted Upper Confidence Bound (MLA-UCB) algorithm.
result Proves to improve cumulative regret even with biased surrogate rewards.
ARC algorithm optimizes dynamic pricing with correlated observations.
problem Optimizing dynamic pricing with correlated and generally distributed observations.
method Extends ARC algorithm to batched bandits with generalised linear model.
result ARC algorithm outperforms alternative approaches in dynamic pricing.
A deep reinforcement learning method for cost-sensitive portfolio selection.
problem Non-stationary price series and complex asset correlations make feature learning hard, and practical cost constraints are not considered.
method A two-stream portfolio policy network and a cost-sensitive reward function are developed using deep reinforcement learning.
result The method achieves superior performance in profitability, cost-sensitivity, and representation abilities.
Unified framework for policy learning using weak supervision.
problem High-quality supervision is often infeasible or expensive in practice.
method Treat weak supervision as imperfect peer information and evaluate policies based on correlated agreement.
result Substantial performance improvements, especially in complex or noisy environments.
Proposes method to discover diverse near-optimal policies in reinforcement learning.
problem Finding different solutions to the same problem in reinforcement learning.
method Formalizes problem as CMDP, uses Successor Features, proposes new diversity rewards.
result Proposed method discovers diverse near-optimal policies that are robust and distinct.
Proposes meTS for efficient exploration in correlated bandits.
problem Efficiently explore in bandits with correlated actions.
method Mixed-effect model with Thompson Sampling.
result Bound on Bayes regret with two terms.
New algorithm uses control variates to improve multi-armed bandit performance.
problem Stochastic multi-armed bandits with auxiliary reward information.
method Developed UCB-CV algorithm using control variates for mean estimation.
result UCB-CV algorithm provides tighter confidence bounds and smaller variance.
Two novel methods identify influential features in CMABs for better reward distribution.
problem Suboptimal features degrade rewards, interpretability, and efficiency in CMABs.
method Heterogeneous Incremental Effect (HIE) and Heterogeneous Distribution Divergence (HDD) methods.
result Consistent ability to identify influential HTE features, enhancing CMAB performance.
Improved CEM for fast real-time planning in high-dimensional control tasks.
problem Sampling inefficiency of CEM in real-time planning.
method Novel additions to CEM including temporally-correlated actions and memory.
result 2.7-22x less samples and 1.2-10x performance increase.
New algorithms boost SAT solver performance by optimizing restart strategies.
problem Optimizing decision-making under time constraints with restarts.
method Developed online learning algorithms for a bandit problem with controlled restarts.
result Achieved O ( log ( τ ) ) O(\log(τ)) O ( log ( τ )) and O ( τ log ( τ ) ) O(\sqrt{τ\log(τ)}) O ( τ log ( τ ) ) regret bounds. Simplifies large action space bandits by selecting representative actions.
problem Efficiently managing large action spaces with correlated outcomes.
method Random sampling and solving of bandit instances to identify representative actions.
result The algorithm selects a smaller set of representative actions that perform nearly as well as the full action space.
This paper proposes an exploration method for deep reinforcement learning based on parameter space noise. Recent studies have experimentally shown that parameter space noise results in better exploration than the commonly used action space noise. Previous methods devised a way to update the diagonal covariance matrix o…
This paper analyzes switchback experiments in A/B testing, revealing key factors affecting their effectiveness.
problem Understanding the effectiveness of different switchback designs in A/B testing.
method Comprehensive comparative analysis of various switchback designs in Markovian environments, covering state-of-the-art RL estimators.
result The effectiveness of switchback designs depends on the size of the carryover effect and reward autocorrelations.
Study non-asymptotic bounds on correlation in high-dimensional linear systems, revealing invariant subspaces and bottlenecks.
problem Understanding correlation and mixing in high-dimensional linear systems with Gaussian noise.
method Sampling from sub-trajectories, using Talagrand's inequality, and analyzing invariant subspaces.
result Large discrepancy between algebraic and geometric multiplicity leads to bottlenecks between invariant subspaces.
A RL framework selects features to balance bias and accuracy dynamically.
problem Bias in automated feature selection when predictors are correlated.
method Multi-component reward function with policy gradient for dynamic regularization and bias mitigation.
result Model balances fairness and accuracy during training.
AGG-UCB uses neural networks to optimize group behaviors in contextual bandits.
problem Optimizing group behaviors in contextual bandits with mutual impacts.
method Introduces Arm Group Graph (AGG) and AGG-UCB algorithm using neural networks and graph neural networks.
result Achieves near-optimal regret bound with over-parameterized neural networks.
We consider a novel multi-armed bandit framework where the rewards obtained by pulling the arms are functions of a common latent random variable. The correlation between arms due to the common random source can be used to design a generalized upper-confidence-bound (UCB) algorithm that identifies certain arms as $non-c…
Paper proposes a new portfolio model for better investment decisions.
problem Traditional portfolio models fail to adapt to nonstationary markets.
method Developed a mean-detrended cross-correlation portfolio model (M-DCCP model).
result The M-DCCP model outperforms traditional models in constructing optimal portfolios.
This work analyzes Q Q Q -learning with adaptive stepsizes for finite-time convergence.
problem Finite-time convergence analysis for average-reward Q Q Q -learning with adaptive stepsizes. method Adaptive stepsizes as local clocks, time-inhomogeneous Markovian reformulation, almost-sure time-varying bounds, conditioning arguments, and Markov chain concentration inequalities.
result Convergence rates of i l d e O ( 1 / k ) ilde{\mathcal{O}}(1/k) i l d e O ( 1/ k ) for mean-square and pointwise mean-square convergence. A new reinforcement learning method reduces action complexity for robust control.
problem Deep reinforcement learning's susceptibility to spurious correlations.
method Minimizing trajectory entropy to encourage simple, predictable actions.
result Trajectory Entropy Reinforcement Learning achieves superior performance and robustness.
Research suggests using deep learning for better recommendation systems.
problem Recommender systems rely on proxies for A/B testing, leading to random success.
method Advocates for using deep learning to improve recommendation performance.
result Deep learning can potentially optimize reward in recommendation systems.