We are most grateful to Andy Barto and to Csaba Szepesvári for careful reading of the manuscript and suggestions on simplifying and clarifying our arguments and proofs. We are also grateful to one of our referees, who identified a missing step in one of the proofs and provided many helpful remarks. This work was supported by the Hungarian National Science Foundation (Grant OTKA 32487) and by EOARD (Grant F61775-00-WE065). Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the European Office of Aerospace Research and Development, Air Force Office of Scientific Research, Air Force Research Laboratory.