  We study a typical optimization model where the optimization variable is
composed of multiple probability distributions. Though the model appears
frequently in practice, such as for policy problems, it lacks specific analysis
in the general setting. For this optimization problem, we propose a new
structural condition/landscape description named generalized quasar-convexity
(GQC) beyond the realms of convexity. In contrast to original quasar-convexity
\citep{hinder2020near}, GQC allows an individual quasar-convex parameter
$\gamma_i$ for each variable block $i$ and the smaller of $\gamma_i$ implies
less block-convexity. To minimize the objective function, we consider a
generalized oracle termed as the internal function that includes the standard
gradient oracle as a special case. We provide optimistic mirror descent (OMD)
for multiple distributions and prove that the algorithm can achieve an adaptive
$\tilde{\mathcal{O}}((\sum_{i=1}^d1/\gamma_i)\epsilon^{-1})$ iteration
complexity to find an $epsilon$-suboptimal global solution without pre-known
the exact values of $\gamma_i$ when the objective admits ``polynomial-like''
structural. Notably, it achieves iteration complexity that does not explicitly
depend on the number of distributions and strictly faster $(\sum_{i=1}^d
1/\gamma_i \text{ v.s. } d\max_{i\in[1:d]} 1/\gamma_i)$ than mirror decent
methods. We also extend GQC to the minimax optimization problem proposing the
generalized quasar-convexity-concavity (GQCC) condition and a decentralized
variant of OMD with regularization. Finally, we show the applications of our
algorithmic framework on discounted Markov Decision Processes problem and
Markov games, which bring new insights on the landscape analysis of
reinforcement learning.
