  We study the problem of synthesizing implementations from temporal logic
specifications that need to work correctly in all environments that can be
represented as transducers with a limited number of states. This problem was
originally defined and studied by Kupferman, Lustig, Vardi, and Yannakakis.
They provide NP and 2-EXPTIME lower and upper bounds (respectively) for the
complexity of this problem, in the size of the transducer. We tighten the gap
by providing a PSPACE lower bound, thereby showing that algorithms for solving
this problem are unlikely to scale to large environment sizes. This result is
somewhat unfortunate as solving this problem enables tackling some high-level
control problems in which an agent has to infer the environment behavior from
observations. To address this observation, we study a modified synthesis
problem in which the synthesized controller must gather information about the
environment's behavior safely. We show that the problem of determining whether
the behavior of such an environment can be safely learned is only
co-NP-complete. Furthermore, in such scenarios, the behavior of the environment
can be learned using a Turing machine that requires at most polynomial space in
the size of the environment's transducer.
