Kernel-based function approximation improves reinforcement learning performance.
problem Average reward reinforcement learning in infinite horizon settings.
method Optimistic algorithm based on kernel ridge regression.
result No-regret performance guarantees and confidence intervals for kernel-based predictions.
A new algorithm for differential privacy in kernelized contextual bandits reduces error rate.
problem Joint differential privacy in kernelized contextual bandits.
method Proposes a novel algorithm with a specific error rate and privacy parameter dependence.
result Achieves an error rate of $\mathcal{O}\left(\sqrt{\frac{γ_T}{T}} + \frac{γ_T}{T \varepsilon}
ight)$ after T T T queries. New algorithm uses GNNs to optimize rewards in graph-structured data.
problem Optimizing rewards in molecule design with graph-structured data.
method Embedding permutation invariance into GNNs and using GNTK for regret bounds.
result First GNN confidence bound and phased-elimination algorithm with sublinear regret.
Unified framework for multi-user bandits using Laplacian kernels.
problem Multi-user contextual bandits with graph-related users and non-linear rewards.
method Joint penalty combining graph smoothness and individual roughness in a unified RKHS.
result Unified multi-user RKHS and effective dimension for regret bounds.
New RL method explores environments without rewards, achieving efficient policy generation.
problem Efficiently exploring unknown environments without predefined rewards.
method Optimistic value-iteration algorithm with kernel and neural function approximations.
result Achieves O ~ ( 1 / ε 2 ) \widetilde{\mathcal{O}}(1 /\varepsilon^2) O ( 1/ ε 2 ) sample complexity for generating policies or equilibria. Study preference-based reinforcement learning in episodic kernel MDPs.
problem Learning from episodic human preferences in reinforcement learning.
method Developed preference-based value estimation and confidence sets for kernel-based MDPs.
result Proved high-probability regret bounds that converge to optimal policy value.
This paper tackles open problem of tight bounds for KBs with Bernoulli rewards.
problem Open problem of tight bounds for Kernelized Bandits with Bernoulli rewards.
method Focus on Bernoulli model, not subgaussian noise, and optimize function in RKHS.
result Open problem remains unsolved in this context.
Kernel ε ε ε -Greedy optimizes multi-armed bandits with covariates for sub-linear regret.
problem Optimizing multi-armed bandits with covariates in a reproducing kernel Hilbert space.
method Online weighted kernel ridge regression estimator for mean reward function estimation.
result Achieves sub-linear regret rate and optimal T \sqrt{T} T regret rate under margin condition. We consider online learning for minimizing regret in unknown, episodic Markov decision processes (MDPs) with continuous states and actions. We develop variants of the UCRL and posterior sampling algorithms that employ nonparametric Gaussian process priors to generalize across the state and action spaces. When the trans…
Kernel-UCBVI algorithm balances exploration and exploitation in metric state-action spaces.
problem Exploration-exploitation dilemma in finite-horizon reinforcement learning with metric state-action spaces.
method Kernel-UCBVI, leveraging smoothness and kernel estimators of rewards and transitions.
result First regret bound for kernel-based RL using smoothing kernels, O ( H 3 K 2 d / ( 2 d + 1 ) ) O(H^3 K^{2d/(2d+1)}) O ( H 3 K 2 d / ( 2 d + 1 ) ) . Optimizes reward learning design for complex tasks using nonparametric methods.
problem Challenges in specifying reward functions for complex tasks.
method Models rewards and policies as nonparametric functions in RKHSs, derives risk bounds, and optimizes query design.
result Derives non-asymptotic excess risk bounds and finite sample statistical rates for reward learning.
Kernel method estimates long-term effects from short-term data.
problem Estimating long-term effects from short-term data in continuous actions.
method Kernel ridge regression to embed and extrapolate long-term effects.
result Uniform consistency and nonasymptotic error bounds for the estimator.
The Artificial Prediction Market is a recent machine learning technique for multi-class classification, inspired from the financial markets. It involves a number of trained market participants that bet on the possible outcomes and are rewarded if they predict correctly. This paper generalizes the scope of the Artificia…
We tackle the problem of online reward maximisation over a large finite set of actions described by their contexts. We focus on the case when the number of actions is too big to sample all of them even once. However we assume that we have access to the similarities between actions' contexts and that the expected reward…
This paper analyzes how randomizing rewards in MBRL can improve performance without being overly optimistic.
problem The gap between theoretical worst-case regret analysis and empirical performance in MBRL.
method Reward randomization in model-based reinforcement learning (MBRL) with kernelized linear regulator (KNR) model.
result Reward randomization guarantees partial optimism and near-optimal worst-case regret.
Kernel-based methods improve policy evaluation in MRP models.
problem Estimating value functions in infinite-horizon discounted MRP models.
method Kernel-based temporal difference methods using reproducing kernel Hilbert spaces.
result Optimal error bounds derived for the kernel-based LSTD estimate.
Algorithm adapts to non-stationary rewards without prior knowledge.
problem Optimizing decisions in non-stationary environments without prior knowledge of changes.
method Optimization-based algorithm that restarts when non-stationarity is detected.
result Achieves tighter dynamic regret bound and is nearly minimax optimal.
Study non-rectangular robust MDPs for average-reward, finding optimal policies and transient values.
problem Non-rectangular robust Markov decision processes under average-reward criterion.
method Proves history-dependent policies are robust-optimal, introduces transient-value framework, constructs epoch-based policy.
result Existence and properties of robust optimal policies, transient value bounds.
New method tackles high-dimensional contextual bandits with flexible kernel models.
problem Maximizing rewards in decision-making scenarios with many features.
method Introduces stochastic assumptions and no-regret learning for Gaussian kernels.
result Achieves no-regret learning even with feature dimensions growing with samples.
New method tackles confounded bandit problems with dual instrumental variables.
problem Confounded contextual bandit problems where noise affects both contexts and rewards.
method Dual instrumental variable regression applied to reproducing kernel Hilbert spaces.
result Near-optimal convergence rate and computationally efficient algorithms proved.
Paper tackles non-stationary kernelized bandits with near-optimal algorithm.
problem Minimizing regret in a time-varying reward function.
method Near-optimal algorithm with a novel restarting phased elimination with random permutation (R-PERP).
result Regret upper bound matches the lower bound, making the algorithm near-optimal.
MAXMINLCB optimizes unknown target functions with preference feedback using a Stackelberg game approach.
problem Optimizing unknown target functions with pairwise comparisons and human feedback.
method MAXMINLCB, a zero-sum Stackelberg game, balances exploration and exploitation.
result MAXMINLCB consistently outperforms existing algorithms with a rate-optimal regret guarantee.
We consider black box optimization of an unknown function in the nonparametric Gaussian process setting when the noise in the observed function values can be heavy tailed. This is in contrast to existing literature that typically assumes sub-Gaussian noise distributions for queries. Under the assumption that the unknow…
Paper proposes Langevin dynamics for adaptive IRL of stochastic gradient algorithms.
problem Estimating reward functions from noisy gradient estimates of stochastic gradient agents.
method Generalized Langevin dynamics algorithm for IRL.
result Proposed algorithms asymptotically generate samples proportional to exp(R(θ)).
New algorithm for differential private kernel bandits with improved regret bounds.
problem Contextual bandits with differential privacy constraints.
method Proposes a private kernel-ridge regression estimator using random projections.
result Achieves state-of-the-art cumulative regret bounds in both joint and local models of differential privacy.
This paper improves understanding of GAIL's generalization and computational efficiency.
problem Understanding the theoretical properties of GAIL, especially its generalization and computational aspects.
method Investigates GAIL's theoretical properties, showing guarantees for generalization and computational efficiency.
result GAIL can be efficiently solved by stochastic first order optimization algorithms with sublinear convergence.
Bayesian optimization improved for biased data.
problem Adversarial bias in observations, especially hidden confounders.
method Reduction to dueling bandits, information-directed sampling (IDS).
result First efficient kernelized algorithm with regret guarantees.
Reward shaping speeds up human learning through IRL.
problem Slow learning in humans, especially for challenging tasks.
method Extended IRL algorithm with kernel methods, conducted experiments with online game players.
result Players learn desired policies more quickly with reward shaping.
Study pure exploration in high-dimensional feature spaces using adaptive embeddings.
problem Overcoming the curse of dimensionality in pure exploration bandits.
method Adaptive embedding of feature representations into lower-dimensional spaces, carefully dealing with model misspecification.
result Sample complexity guarantees that depend on the effective dimension of feature spaces in kernel or neural representations.
Kernelized bandit algorithm tackles adaptive contextual bandits with single-index models.
problem Adaptive contextual bandits with single-index models and unknown link functions.
method Kernelized ε-greedy algorithm combining Stein-based index estimation and kernel ridge regression for reward functions.
result Unified framework for simultaneous learning and inference in single-index contextual bandits.
Improved GP bandit algorithms for noiseless, varying noise, and RKHS norms.
problem Minimizing regret in Gaussian process bandits with unknown reward functions.
method New upper bound on maximum posterior variance, refined MVR and PE algorithms.
result Optimal regret bounds for noiseless, varying noise, and RKHS norms.
We study the regret minimization problem in the novel setting of generalized kernelized bandits (GKBs), where we optimize an unknown function f ∗ f^* f ∗ belonging to a reproducing kernel Hilbert space (RKHS) having access to samples generated by an exponential family (EF) reward model whose mean is a non-linear function $μ(…
IDS optimizes regret in stochastic partial monitoring with linear rewards.
problem Optimizing decision-making in uncertain environments with linear rewards.
method Information Directed Sampling (IDS) for stochastic partial monitoring.
result Achieves optimal regret rates in all observable game regimes.
The success of popular algorithms for deep reinforcement learning, such as policy-gradients and Q-learning, relies heavily on the availability of an informative reward signal at each timestep of the sequential decision-making process. When rewards are only sparsely available during an episode, or a rewarding feedback i…
A novel approach uses an ensemble of Gaussian processes for robust and adaptive reinforcement learning.
problem Adaptive reinforcement learning in large or continuous state spaces.
method Online scalable (OS) approach with a weighted ensemble of Gaussian processes.
result The ensemble approach improves performance in adversarial settings.
A new algorithm for offline RL with trajectory-wise reward reduces bias and variance errors.
problem Offline RL with trajectory-wise reward incurs large bias and variance errors.
method PARTED algorithm that decomposes trajectory return into proxy rewards and performs pessimistic value iteration.
result PARTED achieves provably efficient suboptimality bounds in general MDPs with trajectory-wise reward.
Study improves reinforcement learning for stable long-term performance.
problem Distributionally robust average-reward reinforcement learning for stable long-term performance.
method Proposes two algorithms to achieve near-optimal sample complexity.
result Achieves a sample complexity of O ( ∣ S ∣ ∣ A ∣ t m i x 2 ε − 2 ) O(|\mathbf{S}||\mathbf{A}| t_{\mathrm{mix}}^2\varepsilon^{-2}) O ( ∣ S ∣∣ A ∣ t mix 2 ε − 2 ) for estimating optimal policy and robust average reward. NK bandits improve performance on nonlinear tasks.
problem Improving performance on nonlinear sequential decision tasks.
method Proposed NK bandits using neural kernels to guide policies.
result NK bandits achieve state-of-the-art performance.
Algorithm reduces regret in distributed kernel bandits with shared randomness.
problem Minimizing regret in collaborative function maximization.
method Uniform exploration at local agents and shared randomness with central server.
result Achieves optimal regret order with sublinear communication cost.
We consider the task of Inverse Reinforcement Learning in Contextual Markov Decision Processes (MDPs). In this setting, contexts, which define the reward and transition kernel, are sampled from a distribution. In addition, although the reward is a function of the context, it is not provided to the agent. Instead, the a…
Paper optimizes learning MDPs with adversarial rewards using linear models.
problem Learning MDPs with adversarial rewards and changing reward functions.
method Proposes POWERS, an optimistic policy optimization algorithm.
result Achieves nearly optimal regret bound of O ( d H T ) O(dH\sqrt{T}) O ( d H T ) . New algorithm learns policies without explicit rewards for MDPs.
problem Learning policies for MDPs without explicit rewards.
method UCRL-RFE algorithm with linear function approximation.
result UCRL-RFE achieves optimal policy with minimal exploration samples.
A new method estimates multi-dimensional value distributions using Hilbert space embeddings.
problem Estimating value distributions in complex, multi-dimensional reinforcement learning settings.
method Hilbert space mappings and kernel mean embeddings to estimate the kernel mean embedding of multi-dimensional value distributions.
result Uniform convergence guarantees and robust off-policy evaluation demonstrated in simulations.
New algorithm tackles adversarial RL without horizon constraints.
problem Adversarial reinforcement learning with unknown transition kernel.
method Uses weighted least square estimator and occupancy measure for policy search.
result Achieves near-optimal regret bound of O ( K ) O(\sqrt{K}) O ( K ) . Improved regret bounds for linear bandits with heavy-tailed rewards.
problem Stochastic linear bandits with heavy-tailed rewards.
method Elimination-based algorithm guided by experimental design.
result Regret bound of \(\tilde{\mathcal{O}}(d^\frac{1+3ε}{2(1+ε)} T^\frac{1}{1+ε})\) for \(ε\in (0,1)\).
New algorithms use neural networks to minimize regret in contextual bandits.
problem Minimizing regret in sequential decisions with side information.
method Proposes NN-UCB and NTK-UCB algorithms using neural networks.
result Proves sublinear regret bounds for contextual bandits.
Kernel method improves cooperative decision-making among agents.
problem Cooperative multi-agent decision making with contextual information.
method Proposed extsc{Coop-KernelUCB} algorithm for near-optimal per-agent regret.
result Near-optimal bounds on per-agent regret with efficient computation and communication.
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…