Approximate Dynamic Programming Finally Performs Well in the Game of Tetris
Tetris is a video game that has been widely used as a benchmark for various optimization techniques including approximate dynamic programming (ADP) algorithms. A look at the literature of this game shows that while ADP algorithms that have been (almost) entirely based on approximating the value function (value function based) have performed poorly in Tetris, the methods that search directly in the space of policies by learning the policy parameters using an optimization black box, such as the cross entropy (CE) method, have achieved the best reported results. This makes us conjecture that Tetris is a game in which good policies are easier to represent, and thus, learn than their corresponding value functions. So, in order to obtain a good performance with ADP, we should use ADP algorithms that search in a policy space, instead of the more traditional ones that search in a value function space. In this paper, we put our conjecture to test by applying such an ADP algorithm, called classification-based modified policy iteration (CBMPI), to the game of Tetris. Our experimental results show that for the first time an ADP algorithm, namely CBMPI, obtains the best results reported in the literature for Tetris in both small 10 × 10 and large 10 × 20 boards. Although the CBMPI's results are similar to those of the CE method in the large board, CBMPI uses considerably fewer (almost 1/6) samples (calls to the generative model) than CE.
This paper studies the application of a 
      classifier-based approximate policy iteration algorithm called CBMPI to 
      the game of Tetris, a much studied benchmark task in reinforcement 
      learning. CBMPI is compared to DPI, a variant which omits the regression 
      step used to estimate the value function in CBMPI; lambda-PI, a related 
      policy iteration method which uses eligibility-trace-like backups and 
      omits the classification step of CPMPI; and CE, a policy-search method 
      that is currently the state of the art in Tetris. Experiments are 
      presented on small boards and large boards using different state features, 
      and the best policies across runs for each method are further evaluated 
      across 10,000 games. Though this paper makes no theoretical or 
      algorithmic contribution, the empirical analysis is potentially highly 
      significant. Because this benchmark task is well studied, significantly 
      improving the state of the art is a nontrivial endeavor. In addition, 
      since the state-of-the-art CE approach has high sample complexity, 
      progress getting strong performance from more sample-efficient 
      value-function methods is of substantial interest, especially if the 
      results shed light on *why* previous efforts with value-function methods 
      performed poorly. However, I have two main concerns. First, I find 
      the paper's efforts to address the "why" unsatisfactory. Second, the 
      experimental comparisons are plagued by confounding factors that 
      substantially undermine the validity of the conclusions drawn from them. 
      Regarding the "why", the authors propose that the success of CE 
      suggests that in Tetris, policies may be easier to represent than value 
      functions. That's a reasonable hypothesis, and it is consistent with the 
      folk wisdom that good policies are sometimes simpler than accurate value 
      functions, and that this can give policy search an advantage. However, the 
      authors then suggest that, if this hypothesis holds, a consequence thereof 
      would be that we should employ ADP methods that search in policy space 
      rather than value function space, and they propose CBMPI as a candidate. 
      However, this is essentially an actor-critic method that explicitly 
      represents both the value function and the policy and thus the 
      difficulties of representing a value function have in no way been 
      circumvented. (This is of course true of all ADP methods because if they 
      didn't explicitly represent the value function they would by definition be 
      policy-search methods). It's true that CBMPI conducts a search in policy 
      space for a classifier-based policy that is consistent with estimated 
      Q-values, and that this is different from many ADP methods, but we are 
      never given any argument why this should make Tetris easier to solve and 
      it does not follow from the hypothesis that Tetris policies are easier to 
      represent than value functions that this would be the case. The superior 
      performance of CBMPI to lambda-PI, which does not explicitly search in 
      policy space, would seem to lend credence to the authors' claim (though 
      without addressing the "why") but there are confounding factors in these 
      comparisons (see below) that leave me unconvinced. Regarding the 
      confounding factors, I have the following concerns about the experiments: 
      1. In 2.2, we are told that CBMPI depends on rollouts starting 
      from a set of states sampled from a distribution mu. This already raises 
      questions about comparing to CE, because CBMPI requires a generative model 
      whereas a CE requires only a trajectory model. Then, in 3.1, we learn that 
      the set of states are not sampled from a stationary mu but from the 
      trajectories generated by a strong Tetris policy DU which is assumed to be 
      available as prior knowledge. However, in Appendix A, we are told that 
      lambda-PI was deprived of this prior knowledge and instead used a Dirac on 
      the empty board state. In addition, CE was also deprived of this prior 
      knowledge. Though it is less obvious how CE should make use of this 
      initial policy, one could certainly imagining seeding the initial Gaussian 
      distribution on the basis of it. In my opinion, this raises serious 
      questions about the fairness of the comparisons between CBMPI and 
      lambda-PI and CE. 2. In 3.2.1, we are told that in the small-board 
      experiments using the D-T features, CBMPI was optimized for the feature 
      settings and the best performance was obtained using D-T plus the 5 RBF 
      height features. While the paper is not 100% clear on this matter, as far 
      as I can tell, the other methods used only the D-T features, making the 
      comparisons in Figure 4 potentially very unfair. In Figure 5a-c, where all 
      methods use the same Bertsekas features, we see no performance improvement 
      for CBMPI. In Figure 5d, we again see some performance improvement but 
      here again, though the paper is not explicit about it, as far as I can 
      tell CBMPI is using D-T+5 while the other methods are using only D-T. 
      3. Also regarding 5d: while it's true that CBMPI does better than 
      DPI after 4 iterations, it's also true that DPI does better from 2-4 
      iterations. It's awkward to argue that final performance is what matters 
      (and therefore CBMPI is better than DPI) given that CE outperforms both in 
      the long run. It's fair to say that CBMPI learns better than CE in a short 
      term, but it's misleading to conclude that CBMPI achieved equal 
      performance with fewer samples, because this is true at only specific 
      points on the learning curve. CBMPI is faster but does not equal CE's 
      final performance. 4. Because a few random events can mean the 
      difference between a game that ends quickly and one that lasts hours, 
      Tetris is notorious for having high variance in scores for a given policy. 
      However, none of the experimental results in this paper include any 
      variance analysis, so we have no way of assessing the statistical 
      significance of the performance differences observed in Figures 4 and 5. 
      I'm particularly concerned about the differences presented in Table 1, 
      since I suspect that, for policies that can clear millions of lines per 
      game, the cross-game variance is probably huge. Minor comment: 
      Figures 4 and 5 would be much easier to decipher if the x-axis was 
      samples, not iterations, thereby making it directly possible to fairly 
      compare the methods.