Matrix Toolkits for Java optimised for MDPs

A self-contained  library for  Java that  implements a  number of  operations on
sparse vectors and sparse matrices optimised for POMDPs or MDPs.

A few  years ago, I  started using the original  Matrix Toolkits for  Java (MTJ)


for my POMDP coding. While working on  POMDPs, I realised that I could introduce
many POMDP-related  optimisations if I  could work with  raw data in  the sparse
vectors  and matrices  available  in MTJ.  In this  way,  I implemented  several
extensions to the MTJ library which  are contained in this repository. This code
is based on the MTJ code that I checked out from the main MTJ repository on Sept
18th, 2012. My main changes were in the following classes:

- SparseVector.java (sparse dot products, and  other operations that require raw
  access to data in sparse vectors)
- FlexCompColMatrix.java
- FlexCompRowMatrix.java

This  library  was  used  in  all  my POMDP  papers  published  since  2013.  In
particular, it was useful to obtain competitive performance in this paper:

Marek Grzes  and Pascal Poupart:  Incremental Policy Iteration  with Guaranteed.
Escape from  Local Optima  in POMDP Planning  Proceedings of  the International.
Conference  on  Autonomous Agents  and  Multiagent  Systems (AAMAS).  Istanbul,.
Turkey, 2015                                                                   .

The full source code for this paper is here
https://www.cs.kent.ac.uk/people/staff/mg483/code/IPI/  and it contains  several
examples that show  how to use  the mtj-mdp package. In  particular, this  class
mgjpomdp.solve.ValueIterationMTJ.java   shows  how  to  implement  simple  value
iteration for MDPs.

Also, this  code https://www.cs.kent.ac.uk/people/staff/mg483/code/IsoFreeBB/ is
based on the same MTJ-MDP library.

The  library  is basically  self-contained  for  MDP planning  or  reinforcement
learning. Linear  algebra operations  required external  libraries and  for that
you'd need to check  the requirements of the original MTJ  library. If you would
be interested  in a similar  package for  C++, my guess  is that HSVI2  (a POMDP
planner written in C++)  exploits sparsity in a similar manner.  If you read the
HSVI and  HSVI2 papers, you can  see that POMDP-specific sparse  operations were
implemented in  HSVI2 for better  performance. This is more  or less what  I was
trying  to do  when I  was adding  POMDP-specific sparse  operations to  the MTJ

Marek Grzes

# ----------------------------------------------------------------------------

0. The project files  for IntelliJ Idea and NetBeans are  provided. The best way
   to compile  the project is to  use ant (read  below). ant will also  copy the
   final jar  file to ~/bin. Intellij  Ideas is particularly convenient  to work
   with, but the ant scripts are manged by NetBeans. So, we you'd like to change
   anything related  to ant, you would  need to do that  from NetBeans. IntelliJ
   Idea can then compile the project using ant.

1. In order  to build the  jar file  in NetBeans, it  is sufficient to  open the
   project  in Net  Beans  (last tested  in  7.1), right  click  on the  project
   Matrix  Toolkits  for Java  and  select  build.  This  should build  the  jar
   file  which  should show  up  in  the ./dist/  directory.  The  jar is  named
   Matrix_Toolkits_for_Java.jar by default and includes the source java files.

2. In order  to remove java  files from  the jar file,  right click on  the main
   project, select Properties and then go to Build->Packaging and there you will
   see Exclude from the JAR file, you can add **/*.java there.

3. compiling using ant:

    - ant # will compile everything, run junit tests and build the jar file
    - ant -p # shows all possible targets
    - ant  jar # builds the  jar file only, it  skips junit tests, the  jar file
   will show up in dist/Matrix_Toolkits_for_Java.jar

   Overall if you type:
   ant package
   You will obtain two jar files that can be added to your project.

4. To run all  junit tests from Net  Beans, just right click on  the project and
   select Test. In NB after 7.1 it  should be possible to right-click inside the
   method and chose Run focused test to run one test. In 7.1 it does not work.

5. The use of the TAO matrix (in the current implementation):

   5.1. b'  should be computed  using TAOColumn.transMult(b,b') because  we need
   the dot  product between columns of  TAO and b.  I should not use  TAORow for
   computing b'. I  wound need to implement sparse TAORow.transMult  in the same
   way TAOColumn.mult is implemented.

   5.2. TAORow.mult(alpha,alpha') where alpha and alpha' are double[][]. This is
   efficient due  to sparse dot products  in the SparseVector. For  now, this is
   the only  place where TORow  can be faster  then TAOColumn, I  could consider
   getting rid  of TAORow,  though during augPOMDP  construction, I  get TAORow,
   perhaps I could remove TAOCol.

TODO: SparseVector.set should immediately mask zeros!

TODO: there are some TODOs in the SparseVector class

TODO: it looks that  I could get rid of TAOCol and  use only TAORow. TAORow.mult
   allows computing updates  and I need to implement  sparse TAORow.transMult to
   compute b' efficiently, once  this is done I won't need  TAOCol (see 5). This
   could be really useful when I cannot keep two copies of TAO.