[MaxWilson]

Unrest is not the problem. Did you notice that a province lists the amount of supplies available in the top left bar as well as the amount of supplies used? Look at all of the provinces in your empire to get a feel for how much supply is available in various provinces, and compare that to supplies used. That won't actually help you (much) in invading enemy lands because you don't know the stats for a province until you conquer it (unless you have national spies like Man and Machaka do) but it will give you an idea why you don't want to move a large army into a wasteland for a month.

If you're already in enemy lands and find yourself starving, you may choose to stop and pillage. It gives you (a little) gold and some temporary supplies (to let you make another attack without being starving at the time). I'm not sure what the formula is for how much of each you get so I don't actually know if it's a good idea. The big problem with starvation is morale so if your army is tough enough you may choose to let them starve. The big problem with long-term, repeated starvation is disease which is a different story, but if you're just 20% over on supply usage or something starvation isn't a huge problem.

-Max