Learning in the bit flipping environment I'm looking at the Andrychowicz et al. paper and running through the gauntlet of implementing a DQN and then implementing a DQN with HER.
In this paper, they mention a bit-flipping environment: a state is represented by an element of $[0,1]^n$, and there is a target state in $[0, 1]^n$. The current state is modified by performing action $i \in [n]$ which flips bit $i$. The initial state and target state are both randomly initialized at every episode. The reward is sparse, so there is only a reward if the current state is the same as the target state and is otherwise $-1$.
How is it possible to learn anything in this environment, let alone a good q-function approximation, especially since the target state is changing every episode?
I have a suspicion that I'm misunderstanding what the "state" actually is, and in fact it is a concatenation of the current state and the target state, and this is what's fed into whatever q-function approximator is being trained, but if the approximator had knowledge of both current and target states, shouldn't a quadratic function take care of this problem quickly (by minimizing $(target_{i} - current_{i})^{2}$ for all $i$)?
Edit: After looking at some code on Github, it seems like indeed the input to whatever model is being used as a deep q-network is a concatenation of the current state as well as the target state. Is this correct? Is it also correct that the deep q-network does not need to be very complicated to learn how to solve this task, and that vanilla DQNs could perform well on this task were it not for the problem of rewards being sparse?
 A: 
I have a suspicion that I'm misunderstanding what the "state" actually is, and in fact it is a concatenation of the current state and the target state, and this is what's fed into whatever q-function approximator is being trained, but if the approximator had knowledge of both current and target states, shouldn't a quadratic function take care of this problem quickly (by minimizing $(target_{i} - current_{i})^{2}$ for all $i$)?

You are correct in your suspicion. Yes it is a trivial problem that does not require RL. That is fine, it is a toy problem to demonstrate a learning algorithm, and the same observation can be made on many toy RL problems - gridworlds, cartpole etc. These can all be solved analytically, and the point of using RL is not to solve the problem, but to demonstrate and measure the capabilities of a learning algorithm.

Is it also correct that the deep q-network does not need to be very complicated to learn how to solve this task, and that vanilla DQNs could perform well on this task were it not for the problem of rewards being sparse?

Predicting the future reward from flipping each bit is similar to a XOR problem on each bit. Flipping bits when the state and target are identical pushes the end of episode another step into the future, whilst doing so when the state and target are different is a direct step towards the eventual end. The state value under an optimal policy is simply the negative count of bytes that differ, which is the sum $-\sum_i target_i \oplus current_i$ where $\oplus$ is the XOR operator. The action value is similar.
This should be solvable by a neural network with one hidden layer and same number of neurons as inputs. Adding a few more may make it learn faster and more reliably. Value functions for non-optimal policies during learning may also require a few more neurons because the non-optimal policies will not have such a simple relationship between state and expected return. Even allowing for that, the network architecture should be relatively simple compared to, say, a neural network for solving Pong or Breakout.
The reward is sparse, in that all values except end are the same, but actually it is designed to work well for value prediction from the state when considering the undiscounted return.
