Before revision:  The first is computationally expensive but provably obtains (\sqrt{B_\star^3 d^3 K/c_{min , where B_\star is a (known)upper bound on the optimal cost-to-go function, d is the feature dimension, K is the number of episodes, and c_{min .
After revision:  The first is computationally expensive but provably obtains (\sqrt{B_\star^3 d^3 K/c_{min , is computationally efficient, and uses stationary policies. This is the first LFA algorithm with these three properties, to the best of our knowledge. Our second algorithm improves the regret to \sqrt{K .