Suppose we have many copies of an unknown \(n\)-qubit state \(\rho\).  We measure some copies of \(\rho\) using a known two-outcome measurement \(E_{1}\), then other copies using a measurement \(E_{2}\), and so on.  At each stage \(t\), we generate a current hypothesis \(\omega_{t}\) about the state \(\rho\), using the outcomes of the previous measurements. We show that it is possible to do this in a way that guarantees that \(\left\vert \text{Tr} \!\left( E_{i} \omega_{t}\right) -\text{Tr} \!\left( E_{i}\rho\right) \right\vert \), the error in our prediction for the next measurement, is at least \(\varepsilon\) at most \(\operatorname{O}\!\left( n / \varepsilon^2 \right)\) times. Even in the non-realizable setting – where there could be arbitrary noise in the measurement outcomes – we show how to output hypothesis states that incur at most \(\operatorname{O}( \sqrt {Tn}\;)\) excess loss over the best possible state on the first \(T\) measurements. These results generalize a 2007 theorem by Aaronson on the PAC-learnability of quantum states, to the online and regret-minimization settings. We give three different ways to prove our results – using convex optimization, quantum postselection, and sequential fat-shattering dimension – which have different advantages in terms of parameters and portability.