Many decision-making problems naturally exhibit pronounced structuresinherited from the characteristics of the underlying environment. In a Markovdecision process model, for example, two distinct states can have inherentlyrelated semantics or encode resembling physical state configurations. Thisoften implies locally correlated transition dynamics among the states. In orderto complete a certain task in such environments, the operating agent usuallyneeds to execute a series of temporally and spatially correlated actions.Though there exists a variety of approaches to capture these correlations incontinuous state-action domains, a principled solution for discreteenvironments is missing. In this work, we present a Bayesian learning frameworkbased on P\'olya-Gamma augmentation that enables an analogous reasoning in suchcases. We demonstrate the framework on a number of common decision-makingrelated problems, such as imitation learning, subgoal extraction, systemidentification and Bayesian reinforcement learning. By explicitly modeling theunderlying correlation structures of these problems, the proposed approachyields superior predictive performance compared to correlation-agnostic models,even when trained on data sets that are an order of magnitude smaller in size.