Organisation of the Paper

The paper is organised as follows. Section 2 begins with background material on MDPs, NMRDPs, and existing approaches. Section 3 describes our new approach and Section 4 presents NMRDPP. Sections 5 and 6 report our experimental analysis of the various approaches. Section 7 explains how we used NMRDPP in the competition. Section 8 concludes with remarks about related and future work. Appendix B gives the proofs of the theorems. Most of the material presented is compiled from a series of recent conference and workshop papers [46,47,25,26]. Details of the logic we use to represent rewards may be found in our 2005 paper [41].