With Lunar Ball / Lunar Pool it is actually
possible to create an AI that beats the current TAS(es). Seeing as how those TASes were created almost exclusively with an AI to begin with. (Indeed, the bot was designed to play the game, go to next stage, etc. completely without assistance, which it did, without failure, but I sometimes finetuned its outcomes manually.)
It is possible to beat them, because the features for the AI were chosen with a tradeoff between execution speed and completeness in search for best results. With the current settings,
[1565] NES Lunar Pool by Bisqwit in 23:47.52 took several years of CPU time to calculate (and over a year of user time).
Using an AI to play stand-alone is possible with simple games like Tetris or Sokoban. There exist many
successful algorithms for Tetris AI by now.
It might be possible with simple relatively invariant platform games like SMB1, too, however extremely difficult. For a game like Mega Man or Solomon's Key I don't think it is possible at all. (Solomon's Key combines puzzle with moving actors, hence extra difficulty.) Though I would really like to get to read the source code of someone's attempt! Legend of Kage is likely possible due to its simplicity, assuming that you know the mathematical secrets that make it tick.
Oh, can the AI do rerecording? That matters a great deal. If rerecording cannot be used, then the AI must be able to plan ahead without any mistakes, or to recover from mistakes. A Tetris AI can simulate the game ahead with visual information alone, without rerecording, whereas the Lunar Pool bot relies on rerecording to get feedback on what each angle&velocity combination produces. And is the AI allowed to access the game's RAM to read things like actors' velocities and RNG seed?