Most results for online decision problems with structured concepts, such as trees or cuts, as- sume linear costs. In many settings, how- ever, nonlinear costs are more realistic. Ow- ing to their non-separability, these lead to much harder optimization problems. Going beyond linearity, we address online approx- imation algorithms for structured concepts that allow the cost to be submodular, i.e., nonseparable. In particular, we show regret bounds for three Hannan-consistent strategies that capture different settings. Our results also tighten a regret bound for unconstrained online submodular minimization.