AE-LSVI identifies near-optimal policies in complex systems with minimal data.
problem Identifying near-optimal policies in complex, costly data acquisition systems.
method Combines optimism and pessimism for active exploration in a generative model setting.
result Proves near-optimal policy identification over entire state spaces with polynomial sample complexity.
Sublinear LSVI via LSH reduces runtime to sublinear in actions.
problem Efficiently estimating value functions in reinforcement learning with sublinear runtime.
method Formulated as approximate maximum inner product search, used LSH to solve with sublinear time complexity.
result Sublinear runtime while maintaining LSVI's regret.
Improved gap-dependent bounds for reinforcement learning with linear approximations.
problem Achieving nearly minimax-optimal performance with linear function approximation.
method Developed and analyzed the LSVI-UCB++ algorithm and its concurrent variant.
result First gap-dependent regret bound for nearly minimax-optimal algorithm LSVI-UCB++.
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) / ε).
Efficient RL algorithms for linear function approximation with limited adaptivity constraints.
problem Limited adaptivity in reinforcement learning with linear function approximation.
method Proposed two efficient online RL algorithms for episodic linear Markov decision processes under batch learning and rare policy switch models.
result Achieved efficient regret bounds for both batch learning and rare policy switch models, with substantial reduction in adaptivity.
New RL algorithm tackles nonstationary MDPs with linear approximations and varying rewards.
problem Nonstationary reinforcement learning with evolving reward and state transition functions.
method Developed a new algorithm LSVI-UCB-Restart with periodic restart, and parameter-free Ada-LSVI-UCB-Restart for unknown variation budgets.
result First minimax dynamic regret lower bound for nonstationary linear MDPs and linear MDPs lower bound.
New RL algorithm achieves sublinear regret and constraint violation without simulators.
problem Maximizing reward under utility constraints in large-scale systems.
method Model-free, simulator-free algorithm using LSVI-UCB with primal-dual optimization and soft-max policy.
result Achieves i l d e O ( d 3 H 3 T ) ilde{\mathcal{O}}(\sqrt{d^3H^3T}) i l d e O ( d 3 H 3 T ) regret and i l d e O ( d 3 H 3 T ) ilde{\mathcal{O}}(\sqrt{d^3H^3T}) i l d e O ( d 3 H 3 T ) constraint violation bounds. Logarithmic regret achieved in RL with linear function approximation.
problem Achieving logarithmic regret in reinforcement learning with linear function approximation.
method LSVI-UCB for linear MDP assumption, UCRL-VTR for linear mixture MDP assumption.
result Logarithmic regret bounds established for RL with linear function approximation.
New methods tackle robust reinforcement learning in sparse, corrupted data.
problem Tackles robust reinforcement learning in sparse, corrupted data.
method Proposes actor-critic methods with sparse robust estimator oracles.
result First non-vacuous guarantees in high-dimensional sparse MDPs with single-policy concentrability coverage.
A new RL approach optimizes reserve prices in multi-phase auctions, reducing revenue regret.
problem Optimizing reserve prices in multi-phase second-price auctions with noisy and potentially untruthful bidders.
method Combines RL techniques with buffer periods, a novel algorithm, and LSVI-UCB extension.
result Achieves optimal revenue regret under known and unknown noise conditions.
New framework for reinforcement learning with sporadic state observations.
problem Partial observability in reinforcement learning.
method Action-Triggered Sporadically Traceable Markov Decision Processes (ATST-MDPs).
result Optimistic algorithm achieving regret bound for episodic learning.
New algorithm explores reinforcement learning with noisy data.
problem Exploration in reinforcement learning with complex value functions.
method Randomized exploration with i.i.d. scalar noises and optimistic reward sampling.
result Achieves worst-case regret bound of O ~ ( p o l y ( d E H ) T ) \widetilde{O}(\mathrm{poly}(d_EH)\sqrt{T}) O ( poly ( d E H ) T ) . Paper analyzes distributional reinforcement learning with value function approximation, introducing Bellman unbiasedness and a new algorithm.
problem Improving reinforcement learning by capturing environmental stochasticity and addressing infinite dimensionality.
method Introduces Bellman unbiasedness and proposes SF-LSVI algorithm for provably efficient distributional reinforcement learning.
result Achieves a tight regret bound of O(d_E H^3/2 √K) for distributional reinforcement learning.
Modern Reinforcement Learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational …
We prove a lower bound for feature dimension in linear MDPs and propose a novel dynamics aggregation framework.
problem The limitation of feature dimension in linear MDPs and the need for efficient hierarchical reinforcement learning.
method We propose a novel dynamics aggregation framework based on structural dynamics and design a provably efficient hierarchical reinforcement learning algorithm.
result Our algorithm achieves a regret of i l d e O ( d ψ 3 / 2 H 3 / 2 N T ) ilde{O} ( d_ψ^{3/2} H^{3/2}\sqrt{ N T} ) i l d e O ( d ψ 3/2 H 3/2 N T ) and meets the condition d ψ 3 N ≪ d 3 d_ψ^3 N \ll d^{3} d ψ 3 N ≪ d 3 in most real-world environments. New RL algorithm maximizes CVaR in low-rank MDPs with provable efficiency.
problem Maximizing CVaR in large state spaces with function approximation.
method Upper Confidence Bound (UCB) bonus-driven algorithm for low-rank MDPs.
result Achieves sample complexity of O(H^7 A^2 d^4 / τ^2 ε^2) for ε-optimal CVaR.
New algorithm tackles heavy-tailed rewards in RL with instance-dependent regret bounds.
problem Efficient algorithms for RL with heavy-tailed rewards in large state-action spaces.
method Design of \textsc{Heavy-OFUL} for heavy-tailed linear bandits and \textsc{Heavy-LSVI-UCB} for RL with linear function approximation.
result First instance-dependent regret bounds for heavy-tailed rewards in RL with linear function approximation.