There's an algorithm which makes provably optimal decisions. Unfortunately it's also uncomputable because it relies on Solomonoff Induction, but computable approximations exist. Here it played a partially observable version of the Pacman game in 2010.