Exploration in reinforcement learning when state space is huge
In the Atari paper, an $\epsilon$-greedy strategy is used for state-space exploration. This means that the algorithm makes the deep network learn a greedy strategy to pick an action that maximises the $Q$-value of the current state ($a = max_a Q(s, a; \theta)$. At each time-step in a game, the agent picks an action as per this greedy strategy with probability $1-\epsilon$ and it picks a random action to explore the state-space with probability $\epsilon$. 
The value of $\epsilon$ can be varied depending on whether we want the agent to explore more ($\epsilon$ value high) or learn from its past behaviour more ($\epsilon$ value low). 
In the paper, the authors mention that $\epsilon$ is annealed linearly from 1 to 0.1 over the first million frames, and fixed at 0.1 thereafter.