How to deal with the addition of a new state to the environment during training?
There are several ways to tackle this, although exploration is definitely not a solved problem yet ;)
In general, I believe the right thing to do here is to measure the uncertainty of your policy or Q-value estimates and use that to construct some sort of exploration bonus. An intuitive example is given in Exploration by Random Network Distillation. They make two randomly initialized neural nets, one of which is never updated. At every transition, they feed transition data through both neural nets and use the difference in output between them as an estimate of uncertainty, and this quantity is added to the reward. Then they update the modifiable neural net towards the other one. This way, on a completely novel transition, the two neural nets will likely have very different outputs so the reward will be augmented a lot. Of course, this will hopefully encourage the agent to explore.