Super Mario Bros./Any% Strategy

See i_o_l's WR video for the general strategy. This only goes into detail on the non-obvious things going on.

World 1-1

When you go into the underground section, start holding "right" when Mario has fallen about half the way down and jump as soon as you're able, trying to land on the very edge of the bricks in the middle. The farther to the left you land, the sooner you start accelerating to full speed. When the pipe transition happens, you should have 380 on the timer.

Later just hit the flagpole at the very top. If you have 370 remaining on the timer, the level is flawless.

World 1-2 (Warp to 4-1)

The first difficult part here is jumping over the Koopa with the Goomba directly behind it. The best way to do it is to run at full speed and do a jump where you hold A for 1 to 3 frames and then immediately jump again.

At the end of the level, when you go to the warp zone, you actually do not have to make tight turnaround. Unless you land on the very right edge of the rightmost pipe, you will not lose the framerule if you never slowed down elsewhere. The timer will show 346 on a perfect run.

World 4-1

This level is by far the easiest of the run. Jump at the top of the flagpole and you have a perfect time (340 remaining on the timer).

World 4-2 (Warp to 8-1)

In this level you need to do an alternate pipe glitch. To do this, you must scroll the screen farther to the right than usual so that both level exits are on the screen at once.

To scroll the screen, you must jump backwards into the corner of a block. If you just want to get the glitch, you can do as many backwards jumps as you like and will get the trick quite easily. For a good time you need to limit it to 3 backwards jumps. To save another framerule, that must be made 2 backwards jumps, but this almost requires perfection. A perfect run will show 354 or 355 remaining on the timer.

World 8-1

Even if you do not slow down at all in this level, you may lose a framerule. To get a perfect time in 8-1, you need to previously have altered the walking animation by hitting the star block around the middle of this level. (TODO: The precise mechanism needs to be figured out/explained.)

A perfect run will show 200 remaining on the timer.

World 8-2

A perfect run will end with a 342 on the timer, if you do not use the bullet bill glitch (343 is possible, but yields fireworks), and a high 337 or low 338, if you do use the bullet bill glitch.

A good bullet bill spawn can save up to 2 framerules by flagpole glitching using it.

World 8-3

In this level you need to slow down to prevent the fireworks. You should finish with 242 left.

If you know what framerule you're on, you can predict the pseudorandom enemy patterns. Otherwise you need to get lucky.

World 8-4

This is the only level where the framerule doesn't apply due to how the run is timed, so every frame matters.
Room 1
Just go right and enter the pipe. The piranha plant will mysteriously vanish when you touch it.
Room 2
This is the room with the walljump. When you run off the first pipe while holding B and right all the time, you only have 1 frame to make your next jump. If you briefly press left or just let go of right, you have more leeway at the expense of 1 or 2 frames lost.
The walljump is explained in detail above. You will save about 5 frames if you do the walljump facing left instead of right. Depending on how well you do the walljump, you can expect to lose between 1 to 7 frames if you were facing left.
Room 3
This room has another alternate pipe glitch, but it is much easier than the 4-2 one. It is surprisingly easy to lose lots of frames in this room. At the minimum expect to lose 2-5 frames.
Room 4
Hold A while you wait for Mario to get out of the pipe, this will give you a perfect start. It is easy to lose time on the pipe exit, but losing 0-2 frames is also possible.
Room 5
Hope Bowser doesn't kill your run due to pure randomness and hit the switch as far to the left as possible. To beat the World Record, you need to have 314 or 315 remaining on the timer. 315 is not neccessarily faster than 314. The World Record lost 16 frames in this level.

RTA WR and TAS comparison

RTA WR: 4:57.69 by i_o_l
"RTA rules" TAS: 4:54.28 by HappyLee (converted to RTA timing)
"left+right" TAS: 4:54.03 by HappyLee (converted to RTA timing, uses left+right)
"human theory" TAS: 4:57.07 by HappyLee (bullet bill glitch edited in)
It's important to note that RTA and TAS time the run differently. RTA timing starts when the timer appears in 1-1 and TAS timing starts on reset (197 frames difference). They both end on hitting the axe in 8-4.
Also TAS allows left+right, which is banned in RTA, but RTA allows waiting on the start screen for good RNG without time loss.

Comparison Table
All runs are compared level by level to the "RTA rules" TAS by the number of frames they are slower.

World 1-1
The "RTA rules" TAS saves 1 framerule by doing the flagpole glitch.
World 1-2
The "RTA rules" TAS saves 1 framerule by going through the wall and entering the warp pipe sooner.
World 4-1
The "RTA rules" TAS saves 1 framerule by doing the flagpole glitch.
World 4-2
The "RTA rules" TAS saves 2 framerule by doing a wallclip to get Mario ejected to the right side of the screen instead of doing backwards jumps against blocks. 1 framerule can be saved without a wallclip by doing 2 instead of 3 backwards jumps against blocks.
World 8-1
The "RTA rules" TAS saves 1 framerule by doing the flagpole glitch.
World 8-2
The "RTA rules" TAS saves 1 framerule in this level by using backwards jump acceleration at the beginning of the level.
World 8-3
The "RTA rules" TAS saves 1 framerule by doing the flagpole glitch.
World 8-4
The "RTA rules" TAS saves 37 frames:
21 frames come from backwards jump acceleration.
16 frames come from cleaner execution.