4 papers
Stochastic Shortest Path with Sparse Adversarial Costs
Emmeran Johnson, Alberto Rumi, Ciara Pike-Burke +1
We study the adversarial Stochastic Shortest Path (SSP) problem with sparse costs under full-information feedback. In the known transition setting, existing bounds based on Online…
On the necessity of adaptive regularisation:Optimal anytime online learning on -balls
Emmeran Johnson, David Martínez-Rubio, Ciara Pike-Burke +1
We study online convex optimization on -balls in for . While always sub-linear, the optimal regret exhibits a shift between the high-dimensional setti…
Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity
Emmeran Johnson, Ciara Pike-Burke, Patrick Rebeschini
We theoretically explore the relationship between sample-efficiency and adaptivity in reinforcement learning. An algorithm is sample-efficient if it uses a number of queries to…
Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes
Emmeran Johnson, Ciara Pike-Burke, Patrick Rebeschini
Policy Mirror Descent (PMD) is a general family of algorithms that covers a wide range of novel and fundamental methods in reinforcement learning. Motivated by the instability of p…