Are all decks reshuffled if cards run out?

For example the Environment deck. When that runs out of cards is that reshuffled? How about a hero's deck of cards?

Yes to all decks.

This isn't a game where you could run out of cards.

Well, I mean if the environment deck runs out, you shuffle that deck. You don't have to also shuffle the hero and villain decks

And remember, you don't reshuffle just because you ran out of cards in a deck, you reshuffle when you have to draw and there aren't enough cards to do it. It's a subtle distinction, but important. 

You could have known this by looking at akash-buta's flip condition.

Or the Matriarch's ;).

Thankfully, you asked the Sentinels community instead of remaining confused.  We don't want to assume that you've purchased the Rook City or Infernal Relics expansions already!

You shuffle the discard into a new deck whenever an empty deck requires a card being drawn ("you may..." does not mean you have to draw), when a card is discarded from the top of the deck, and when a card must be played from the deck.  This is true for all decks (though villain/environment decks don't draw cards).

And as an addendum, cards which tell you to reveal cards from the top of the deck don't make you reshuffle - you just reveal what's there, and if what you're looking for isn't there then you stop.