31 citations · 83 across the 30 of their papers we have counts for
30 papers
End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions
Zakaria Mhammedi, Alexander Rakhlin, Nneka Okolo
We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying \emph{linear Bellman completeness} -- a fundamental setting w…
Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration
Zakaria Mhammedi, James Cohan
The process of discovery requires active exploration -- the act of collecting new and informative data. However, efficient autonomous exploration remains a major unsolved problem.…
Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization
Ruichen Jiang, Zakaria Mhammedi, Mehryar Mohri +1
We study online linear optimization with matrix variables constrained by the operator norm, a setting where the geometry renders designing data-dependent and efficient adaptive alg…
Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration
Dylan J. Foster, Zakaria Mhammedi, Dhruv Rohatgi
Language model alignment (or, reinforcement learning) techniques that leverage active exploration -- deliberately encouraging the model to produce diverse, informative responses --…
Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback
Haolin Liu, Zakaria Mhammedi, Chen-Yu Wei +1
We consider regret minimization in low-rank MDPs with fixed transition and adversarial losses. Previous work has investigated this problem under either full-information loss feedba…
Reinforcement Learning under Latent Dynamics: Toward Statistical and Algorithmic Modularity
Philip Amortila, Dylan J. Foster, Nan Jiang +2
Real-world applications of reinforcement learning often involve environments where agents operate on complex, high-dimensional observations, but the underlying (''latent'') dynamic…
Online Convex Optimization with a Separation Oracle
Zakaria Mhammedi
In this paper, we introduce a new projection-free algorithm for Online Convex Optimization (OCO) with a state-of-the-art regret guarantee among separation-based algorithms. Existin…
Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
Zakaria Mhammedi
Designing sample-efficient and computationally feasible reinforcement learning (RL) algorithms is particularly challenging in environments with large or infinite state and action s…
Improved Sample Complexity of Imitation Learning for Barrier Model Predictive Control
Daniel Pfrommer, Swati Padmanabhan, Kwangjun Ahn +4
Recent work in imitation learning has shown that having an expert controller that is both suitably smooth and stable enables stronger guarantees on the performance of the learned c…
Fully Unconstrained Online Learning
Ashok Cutkosky, Zakaria Mhammedi
We provide an online learning algorithm that obtains regret on -Lipschitz convex losses for any comparison…
The Power of Resets in Online Reinforcement Learning
Zakaria Mhammedi, Dylan J. Foster, Alexander Rakhlin
Simulators are a pervasive tool in reinforcement learning, but most existing algorithms cannot efficiently exploit simulator access -- particularly in high-dimensional domains that…
Efficient Model-Free Exploration in Low-Rank MDPs
Zakaria Mhammedi, Adam Block, Dylan J. Foster +1
A major challenge in reinforcement learning is to develop practical, sample-efficient algorithms for exploration in high-dimensional domains where generalization and function appro…
Projection-Free Online Convex Optimization via Efficient Newton Iterations
Khashayar Gatmiry, Zakaria Mhammedi
This paper presents new projection-free algorithms for Online Convex Optimization (OCO) over a convex domain . Classical OCO algorithms (such as O…
On the Sample Complexity of Imitation Learning for Smoothed Model Predictive Control
Daniel Pfrommer, Swati Padmanabhan, Kwangjun Ahn +4
Recent work in imitation learning has shown that having an expert controller that is both suitably smooth and stable enables stronger guarantees on the performance of the learned c…
Exponential Stochastic Inequality
Peter D. Grünwald, Muriel F. Pérez-Ortiz, Zakaria Mhammedi
We develop the concept of exponential stochastic inequality (ESI), a novel notation that simultaneously captures high-probability and in-expectation statements. It is especially we…
Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL
Zakaria Mhammedi, Dylan J. Foster, Alexander Rakhlin
We study the design of sample-efficient algorithms for reinforcement learning in the presence of rich, high-dimensional observations, formalized via the Block MDP problem. Existing…
Quasi-Newton Steps for Efficient Online Exp-Concave Optimization
Zakaria Mhammedi, Khashayar Gatmiry
The aim of this paper is to design computationally-efficient and optimal algorithms for the online and stochastic exp-concave optimization settings. Typical algorithms for these se…
Model Predictive Control via On-Policy Imitation Learning
Kwangjun Ahn, Zakaria Mhammedi, Horia Mania +2
In this paper, we leverage the rapid advances in imitation learning, a topic of intense recent focus in the Reinforcement Learning (RL) literature, to develop new sample complexity…
Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning
Zakaria Mhammedi
In this paper, we develop new efficient projection-free algorithms for Online Convex Optimization (OCO). Online Gradient Descent (OGD) is an example of a classical OCO algorithm th…
Damped Online Newton Step for Portfolio Selection
Zakaria Mhammedi, Alexander Rakhlin
We revisit the classic online portfolio selection problem, where at each round a learner selects a distribution over a set of portfolios to allocate its wealth. It is known that fo…
Efficient Projection-Free Online Convex Optimization with Membership Oracle
Zakaria Mhammedi
In constrained convex optimization, existing methods based on the ellipsoid or cutting plane method do not scale well with the dimension of the ambient space. Alternative approache…
Risk-Monotonicity in Statistical Learning
Zakaria Mhammedi
Acquisition of data is a difficult task in many applications of machine learning, and it is only natural that one hopes and expects the population risk to decrease (better performa…
Learning the Linear Quadratic Regulator from Nonlinear Observations
Zakaria Mhammedi, Dylan J. Foster, Max Simchowitz +5
We introduce a new problem setting for continuous control called the LQR with Rich Observations, or RichLQR. In our setting, the environment is summarized by a low-dimensional cont…
PAC-Bayesian Bound for the Conditional Value at Risk
Zakaria Mhammedi, Benjamin Guedj, Robert C. Williamson
Conditional Value at Risk (CVaR) is a family of "coherent risk measures" which generalize the traditional mathematical expectation. Widely used in mathematical finance, it is garne…