1. INTRODUCTION

Efficient reinforcement learning requires to model the environment. What is an efficient strategy for acquiring a model of a non-deterministic Markov environment (NME)? Reinforcement driven information acquisistion (RDIA), the method described in this paper, extends previous work on ``query learning'' and ``experimental design'' (see e.g. [3] for an overview, see [1,6,4,7,2] for more recent contributions) and ``active exploration'', e.g. [9,8,11]. The method combines the notion of information gain with the notion of reinforcement learning. The latter is used to devise exploration strategies that maximize the former. Experiments demonstrate significant advantages of RDIA.

Basic set-up / Q-Learning. An agent lives in a NME. At a given discrete time step $t$, the environment is in state $S(t)$ (one of $n$ possible states $S_1, S_2, ... S_n$), and the agent executes action $a(t)$ (one of $m$ possible actions $a_1, a_2, ... a_m$). This affects the environmental state: If $S(t) = S_i$ and $a(t) = a_j$, then with probability $p_{ijk}$, $S(t+1) = S_k$. At certain times $t$, there is reinforcement $R(t)$. At time $t$, the goal is to maximize the discounted sum of future reinforcement $\sum_{k = 0}^{m} \gamma^{k} R(t+k+1)$ (where $0 < \gamma < 1$). We use Watkins' Q-learning [12] for this purpose: $Q(S,a)$ is the agent's evaluation (initially zero) corresponding to the state/action pair $(S,a)$. The central loop of the algorithm is as follows:

1. Observe current state $S(t)$. Randomly choose $p \in [0, \ldots, 1]$. If $p \leq \mu \in \left[0, \ldots, 1 \right]$, randomly pick $a(t)$. Otherwise pick $a(t)$ such that $Q(S(t), a(t))$ is maximal.

2. Execute $a(t)$, observe $S(t+1)$ and $D(t)$.

3.

$$Q(S(t), a(t)) \leftarrow (1- \alpha) Q(S(t), a(t)) + \alpha (D(t) + \gamma~ max_b Q(S(t+1), b)),$$

where $0 < \gamma < 1 , 0 < \alpha < 1$. Goto 1.

Back to Active Learning - Exploration - Curiosity page
Back to Reinforcement Learning page