Diablo III: Where can Bandit Shrines be found?
Solution 1:
The most telling evidence I could find was from patch notes for patch 2.4 where they list an update for bandit shrine appearances under the "Adventure Mode" section. I can tell you, only from experience, that they do not appear in rifts (nor story mode).
The Diablo wiki states that they were added in patch 2.3 but I couldn't find anything in the notes about it (sometimes Blizzard seems to keep some things a surprise).
Note that while you won't find a bandit shrine in a rift, you can instead find goblin packs, which can be just as rewarding.