When the state-action space is huge I know I can use function approximators to generalize but how can I explore? Doing an exhaustive search seems very naive. What DeepMind for example did to explore the state-action space in Atari games?
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.