I think (but I'm not in 100% sure) I have seen something similar to your problem and it was a simple algorithm playing GO or chess. I would recommend you to search for something like: UCT: Bandit based Monte-Carlo planning in games by Levente Kocsis and Csaba Szepesvari. In Bandit based Monte-Carlo Planning 9th reference points to UCT.
Ad. 1: Maximum reward would be an ultimate win. Probably you won't have game states to expand, but you would rather stay in a single state (that's not a problem) and try to make single optimal move. The more rewarding a particular arm is, the more often it will be used.
Ad. 2: The history for each arm is stored as an oridnary fraction.
Ad. 3: That could be a bit problematic. The decision of which arm to try in next move is based on the fractions mentioned above. If k is not so big, it would be fairly possible to make more or less proper decisions in advance, but generally I think that should be impossible to decide how to make optimal moves in advance, because with each move we discover more knowledge about the game.