  We formulate general definitions of semi-classical gauge transformations for
noncommutative gauge theories in general backgrounds of string theory, and give
novel explicit constructions using techniques based on symplectic embeddings of
almost Poisson structures. In the absence of fluxes the gauge symmetries close
a Poisson gauge algebra and their action is governed by a $P_\infty$-algebra
which we construct explicitly from the symplectic embedding. In curved
backgrounds they close a field dependent gauge algebra governed by an
$L_\infty$-algebra which is not a $P_\infty$-algebra. Our technique produces
new all orders constructions which are significantly simpler compared to
previous approaches, and we illustrate its applicability in several examples of
interest in noncommutative field theory and gravity. We further show that our
symplectic embeddings naturally define a $P_\infty$-structure on the exterior
algebra of differential forms on a generic almost Poisson manifold, which
generalizes earlier constructions of differential graded Poisson algebras, and
suggests a new approach to defining noncommutative gauge theories beyond the
gauge sector and the semi-classical limit based on $A_\infty$-algebras.
