We assign each action the regret r associated with taking that action under the current policy as a cost: The "rolling out" procedure means we naively have to visit O(t 2 ) states each iteration instead of t, where t is the length of a trajectory.
the highly constrained action space described in section 3.1 combined with the use of memoization allows the algorithm to still run efficiently.