Paper improves sparse linear bandits by accounting for noise variance.
problem Sparse linear bandits with unknown noise variance.
method Develops a general framework to convert variance-aware algorithms to sparse linear bandits.
result Achieves $\widetilde{\mathcal O}\left(\sqrt{d\sum_{t=1}^T σ_t^2} + 1
ight)$ regret, interpolating between worst-case and benign settings.
Optimizes ranking from click feedback in a bandit setting.
problem Learning to rank from Bernoulli click feedback in a bandit setting.
method Variance-aware confidence sets derived from Bernstein and Chernoff bounds for optimal algorithms.
result Optimal algorithms for the case of small mean rewards, improving on previous suboptimal results.
New algorithm resists corruption in linear contextual bandits.
problem Adversarial corruption in linear contextual bandits.
method Variance-aware algorithm with multi-level partition and adaptive confidence sets.
result Regret bound of i l d e O ( C 2 d ∑ t = 1 T σ t 2 + C 2 R d T ) ilde{O}(C^2d\sqrt{\sum_{t = 1}^T σ_t^2} + C^2R\sqrt{dT}) i l d e O ( C 2 d ∑ t = 1 T σ t 2 + C 2 R d T ) . FGTSVA improves Thompson Sampling for contextual bandits with optimal variance-aware regret.
problem Optimizing regret bounds for Thompson Sampling in contextual bandits.
method Developed FGTSVA, a variance-aware Thompson Sampling algorithm for contextual bandits with a new decoupling coefficient.
result Achieved optimal regret bound of i l d e O ( d c ⋅ log ∣ F ∣ ∑ t = 1 T σ t 2 + d c ) ilde{O}(\sqrt{\mathrm{dc}\cdot\log|\mathcal{F}|\sum_{t=1}^Tσ_t^2}+\mathrm{dc}) i l d e O ( dc ⋅ log ∣ F ∣ ∑ t = 1 T σ t 2 + dc ) . UCB-V algorithm improves on UCB for MAB problems with variance estimates.
problem Optimizing arm selection in MAB problems with variance information.
method Asymptotic and high probability analysis of UCB-V algorithm.
result UCB-V can exhibit instability in arm-pulling rates but achieves refined regret bounds.
Neural- σ 2 σ^2 σ 2 -LinearUCB improves regret in neural contextual bandits.
problem Balancing exploration and exploitation in neural contextual bandits.
method Proposes a variance-aware neural UCB algorithm using neural representations and an upper bound of reward noise variance.
result Oracle and practical versions of Neural- σ 2 σ^2 σ 2 -LinearUCB achieve better regret guarantees and performance. Improved regret bound for MNL MDPs with variance-aware approach.
problem Optimal reinforcement learning for MNL MDPs with structured variance.
method Introducing a problem-dependent constant measuring average variance, proposing an algorithm with improved regret bound.
result Minimax optimal regret bound of O ( d H 2 σ ˉ T T ) O(dH^2\barσ_T\sqrt{T}) O ( d H 2 σ ˉ T T ) for structured MDPs. Faster convergence of kernel mean embeddings using variance information.
problem Speeding up the convergence rate of kernel mean embeddings.
method Leveraging variance information in reproducing kernel Hilbert space and estimating variance from data.
result Efficiently estimate variance information from data to achieve distribution-agnostic convergence bounds.
VA-OPE improves OPE by incorporating variance information, achieving tighter error bounds.
problem Estimating value function of a target policy from offline data collected by a behavior policy.
method Proposes VA-OPE, an algorithm that reweights Bellman residual using estimated variance of the value function.
result Achieves a tighter error bound than the best-known result.
A new method resolves non-identifiability in reward modeling using anchor labels.
problem Non-identifiability in reward modeling from pairwise preferences alone.
method Anchor-guided Variance-aware Reward Modeling (AVRM) framework.
result AVRM resolves non-identifiability and improves reward modeling performance.
New algorithms reduce dueling bandits' regret with neural networks and efficient exploration.
problem Optimizing dueling bandits with neural networks for better performance.
method Combines shallow exploration strategies with neural networks for utility approximation, using iterative self-improvement and spectral analysis to reduce network width.
result Achieves sublinear regret of O ~ ( d ∑ t = 1 T σ t 2 + d T ) \widetilde{\mathcal{O}}(d\sqrt{\sum_{t=1}^{T} σ_t^2} + \sqrt{dT}) O ( d ∑ t = 1 T σ t 2 + d T ) . This paper addresses dueling bandits with contextual information, improving regret bounds by accounting for variance.
problem Minimizing cumulative regret in dueling bandits with contextual information.
method Proposes a new SupLinUCB-type algorithm for contextual dueling bandits with variance-aware regret bound.
result Achieves a variance-aware regret bound of i l d e O ( d ∑ t = 1 T σ t 2 + d ) ilde O\big(d\sqrt{\sum_{t=1}^Tσ_t^2} + d\big) i l d e O ( d ∑ t = 1 T σ t 2 + d ) . New algorithms reduce regret in online MDPs by adapting to data and variance.
problem Adapting to both adversarial and stochastic environments in online MDPs.
method Develops algorithms based on global optimization and policy optimization, using optimistic follow-the-regularized-leader with log-barrier regularization.
result Achieves refined data-dependent and variance-dependent regret bounds.
New algorithm reduces MDP regret by accounting for state suboptimality gaps and variance.
problem Reducing regret in episodic MDPs with varying state suboptimality gaps.
method Introduced MVP algorithm with variance-aware gap-dependent regret bound.
result Achieved a variance-aware gap-dependent regret bound for MDPs.
Two algorithms tackle heavy-tailed rewards in reinforcement learning with linear function approximation.
problem Online sequential decision-making with heavy-tailed rewards.
method AdaOFUL and VARA algorithms for linear stochastic bandits and MDPs, using modified adaptive Huber regression.
result Achieved state-of-the-art and variance-aware regret bounds for heavy-tailed rewards.
VA-LUCB identifies best arm with variance constraint, achieving optimal sample complexity.
problem Identifying the best arm with variance constraint under fixed confidence.
method Parameter-free algorithm VA-LUCB, analyzing sample complexity and proving lower bounds.
result Optimal sample complexity up to a logarithmic factor in H V A H_{VA} H V A , demonstrated by experiments. RAVEN-UCB addresses non-stationary MAB problems with tighter regret bounds.
problem Non-stationary environments in multi-armed bandits.
method Combines variance-aware adaptation with three innovations: confidence bounds, adaptive control, and recursive updates.
result Achieves tighter regret bounds than UCB1 and UCB-V.
Study on online regression with noise, achieving near-optimal regret bounds.
problem Online generalized linear regression with stochastic noise.
method Sharp analysis of FTRL algorithm for stochastic label noise.
result Achieved near-optimal regret bounds for O ( σ 2 d log T ) + o ( log T ) O(σ^2 d \log T) + o(\log T) O ( σ 2 d log T ) + o ( log T ) . New method improves treatment effect estimation in adaptive experiments with noncompliance.
problem Estimating average treatment effect in adaptive experiments with binary instrumental variable.
method AMRIV estimator that balances outcome noise and compliance variability.
result AMRIV achieves semiparametric efficiency bound and is robust to noncompliance.
Efficient RL for linear MDPs with unknown transitions.
problem Long planning horizons and unknown state transitions in linear mixture MDPs.
method Horizon-free algorithm using weighted least squares with variance and uncertainty awareness.
result Achieves optimal regret up to logarithmic factors.
New algorithm reduces regret in linear mixture SSPs without cost bounds.
problem Learning optimal paths in stochastic environments with cost constraints.
method Extended value iteration with variance-aware confidence set.
result Achieves nearly minimax optimal regret bound of O ( d B ∗ K ) O(dB_*\sqrt{K}) O ( d B ∗ K ) . An algorithm for efficient experimentation in a dynamic environment with personalized preferences and context drifts.
problem Efficiently recommending decisions to users with personalized preferences in a context where the environment is changing over time.
method Dri-MED, inspired from the linear version of the MED strategy, adapted to handle non-stationary heteroskedastic noise.
result The instance-dependent regret scales as $ ilde{\mathcal O}\left(\fracκ{ ildeΔ}d^2(\log(T)
ight)$ , with i l d e Δ ildeΔ i l d e Δ being the constraint-aware sub-optimality gap. New algorithm reduces heavy-tailed linear bandits' computational cost.
problem Stochastic linear bandits with heavy-tailed noise.
method One-pass online mirror descent with adaptive Huber regression.
result Near-optimal regret bound with reduced computational cost.
Improved privacy in RL with near-optimal regret bounds.
problem Privacy-preserving reinforcement learning in personalized decision-making systems.
method Differentially private algorithm based on LSVI-UCB++ with privacy-preserving techniques.
result Achieved a near-optimal regret bound of O(d * sqrt(H^3 * K) + H^(15/4) * d^(7/6) * K^(1/2) / ε).
The problem of reinforcement learning in an unknown and discrete Markov Decision Process (MDP) under the average-reward criterion is considered, when the learner interacts with the system in a single stream of observations, starting from an initial state without any reset. We revisit the minimax lower bound for that pr…
Paper improves CMAB regret bounds by reducing batch-size dependency.
problem Reducing batch-size dependency in combinatorial semi-bandits.
method Developed BCUCB-T and SESCB algorithms with new TPVM conditions.
result Significantly improved regret bounds for various applications.
UCRL3 improves UCRL2's efficiency in reinforcement learning by reducing exploration.
problem Long burn-in phases in numerical experiments of UCRL2.
method UCRL3 uses state-of-the-art time-uniform concentration inequalities and adaptive support computation to tighten exploration.
result UCRL3 achieves a better numerical improvement over UCRL2 in standard environments.
Study tight offline learning bounds for linear MDPs using variance information.
problem Understanding statistical limits with linear function representations in offline reinforcement learning.
method Variance-aware pessimistic value iteration (VAPVI) that reweights Bellman residuals based on estimated variances.
result Improved offline learning bounds expressed in terms of system quantities.
Paper addresses theoretical risks in neural MCCFR, proposing Robust Deep MCCFR for improved performance.
problem Theoretical risks in neural MCCFR, especially in large games.
method Adaptive framework with selective component deployment, including target networks, exploration, and variance-aware training.
result Robust Deep MCCFR achieves significant exploitability improvements in both Kuhn and Leduc Poker.
New algorithm reduces dynamic regret for MDPs with unknown transition and adversarial rewards.
problem Episodic linear mixture MDPs with unknown transition and adversarial rewards.
method Combines occupancy-measure-based global optimization and policy-based variance-aware value-targeted regression.
result Achieves near-optimal dynamic regret of O ~ ( d H 3 K + H K ( H + P ˉ K ) ) \widetilde{\mathcal{O}}(d \sqrt{H^3 K} + \sqrt{HK(H + \bar{P}_K)}) O ( d H 3 K + H K ( H + P ˉ K ) ) . New algorithm reduces regret for linear bandits with unknown noise variance.
problem Finding optimal actions in linear bandits with varying noise variance.
method Adaptive algorithm with Freedman-type concentration inequality and multi-layer structure.
result Achieves i l d e O ( d ∑ k = 1 K σ k 2 + d ) ilde{O}(d \sqrt{\sum_{k = 1}^K σ_k^2} + d) i l d e O ( d ∑ k = 1 K σ k 2 + d ) regret for linear bandits.