  There is significant interest in learning and optimizing a complex system
composed of multiple sub-components, where these components may be agents or
autonomous sensors. Among the rich literature on this topic, agent-based and
domain-specific simulations can capture complex dynamics and subgroup
interaction, but optimizing over such simulations can be computationally and
algorithmically challenging. Bayesian approaches, such as Gaussian processes
(GPs), can be used to learn a computationally tractable approximation to the
underlying dynamics but typically neglect the detailed information about
subgroups in the complicated system. We attempt to find the best of both worlds
by proposing the idea of decomposed feedback, which captures group-based
heterogeneity and dynamics. We introduce a novel decomposed GP regression to
incorporate the subgroup decomposed feedback. Our modified regression has
provably lower variance -- and thus a more accurate posterior -- compared to
previous approaches; it also allows us to introduce a decomposed GP-UCB
optimization algorithm that leverages subgroup feedback. The Bayesian nature of
our method makes the optimization algorithm trackable with a theoretical
guarantee on convergence and no-regret property. To demonstrate the wide
applicability of this work, we execute our algorithm on two disparate social
problems: infectious disease control in a heterogeneous population and
allocation of distributed weather sensors. Experimental results show that our
new method provides significant improvement compared to the state-of-the-art.
