13 citations · 29 across the 27 of their papers we have counts for
4 papers · 1 filter
Learning in Observable POMDPs, without Computationally Intractable Oracles
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Much of reinforcement learning theory is built on top of oracles that are computationally hard to implement. Specifically for learning near-optimal policies in Partially Observable…
Provably Auditing Ordinary Least Squares in Low Dimensions
Ankur Moitra, Dhruv Rohatgi
Measuring the stability of conclusions derived from Ordinary Least Squares linear regression is critically important, but most metrics either only measure local stability (i.e. aga…
Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs
Jonathan A. Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression with ill-conditioned Gaussian random designs is widely believed to exhibit a statistical/computational gap, but there is surprisingly little formal evidenc…
Planning in Observable POMDPs in Quasipolynomial Time
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Partially Observable Markov Decision Processes (POMDPs) are a natural and general model in reinforcement learning that take into account the agent's uncertainty about its current s…