I feed my mantises about 3 times per week on average, sometimes more, sometimes less. If they're not hungry they'll let me know by literally throwing the food back from their holes.

I've had ones in the past that liked feeder fish (rosies/tuffies or guppies), but don't feed those anymore.
I buy shellfish from the supermarket for the basic diet. (If it's safe for human consuption it's as safe as any shellfish could be, I think.) I find that the grayish-white steamer clams (with stripey shells) can live for a long time in my tanks, so I keep some in the peacock tanks at all times so the mantises can eat when they want. I sometimes feed mussels, but if they are dead the mantis won't eat them, and if they are alive the mantis will only eat one so the rest die. (I'm getting famous at Safeway for buying fifty cents worth of seafood.) Only buy shellfish with closed shells, rinse them before adding to the tank, and immediately remove dead ones. Dead ones pollute the tanks pretty badly, and the live ones aren't very clean either. But then, mantis shrimp are messy eaters, so the tanks need to be cleaned more often than other SW tanks.
For the rest of the diet, I buy frozen krill and silversides. Some of the mantises refuse the krill half the time, and I don't know what's up with that. I can get small and large silversides locally, which is great because I have small and large mantises. Once the fishing seasons open up around here I'll be catching live shrimp and shellfish to try on the mantis shrimps, too. If you do this, watch out for areas restricted from fishing for red tides or other safety concerns.
Jennifer