  This paper introduces a framework for Planning while Learning where an agent
is given a goal to achieve in an environment whose behavior is only partially
known to the agent. We discuss the tractability of various plan-design
processes. We show that for a large natural class of Planning while Learning
systems, a plan can be presented and verified in a reasonable time. However,
coming up algorithmically with a plan, even for simple classes of systems is
apparently intractable. We emphasize the role of off-line plan-design
processes, and show that, in most natural cases, the verification (projection)
part can be carried out in an efficient algorithmic manner.
