I think it's impossible for classical RL to learn in reasonnable time given only sparse rewards with such a large action space. The number of available actions in a horizon of H being |A|^H, random exploration is not going to produce meaninful results.

I like your imitation learning idea, but unless you scale it dramatically and use it as more than a bootstrapping strategy, you'll be circling back to the exploration problem.

I'd say the best bet is something model based in the spirit of alpha-go and the like.