Signal Processing - November 2017 - 28

been applied to, ranging from playing video games [47] to indoor
navigation [100].

Reward-driven behavior
Before examining the contributions of deep neural networks to
RL, we will introduce the field of RL in general. The essence of
RL is learning through interaction. An RL agent interacts with
its environment and, upon observing the consequences of its
actions, can learn to alter its own behavior in response to rewards
received. This paradigm of trial-and-error learning has its roots
in behaviorist psychology and is one of the main foundations of
RL [78]. The other key influence on RL is o- ptimal control, which
has lent the mathematical formalisms (most notably dynamic
programming [6]) that underpin the field.
In the RL setup, an autonomous agent, controlled by a
machine-learning algorithm, observes a state s t from its environment at time step t. The agent interacts with the environment by taking an action a t in state s t . When the agent takes
an action, the environment and the agent transition to a new
state, s t + 1, based on the current state and the chosen action.
The state is a sufficient statistic of the environment and thereby comprises all the necessary information for the agent to
take the best action, which can include parts of the agent such
as the position of its actuators and sensors. In the optimal control literature, states and actions are often denoted by x t and
u t, respectively.
The best sequence of actions is determined by the rewards
provided by the environment. Every time the environment transitions to a new state, it also provides a scalar reward rt +1 to
the agent as feedback. The goal of the agent is to learn a policy
(control strategy) r that maximizes the expected return (cumulative, discounted reward). Given a state, a policy returns an action

to perform; an optimal policy is any policy that maximizes the
expected return in the environment. In this respect, RL aims to
solve the same problem as optimal control. However, the challenge in RL is that the agent needs to learn about the consequences of actions in the environment by trial and error, as, unlike in
optimal control, a model of the state transition dynamics is not
available to the agent. Every interaction with the environment
yields information, which the agent uses to update its knowledge.
This perception-action-learning loop is illustrated in Figure 2.

Markov decision processes
Formally, RL can be described as a Markov decision process
(MDP), which consists of
■■ a set of states S, plus a distribution of starting states p (s 0)
■■ a set of actions A
■■ transition dynamics T (s t +1 | s t, a t) that map a state-action
pair at time t onto a distribution of states at time t + 1
■■ an immediate/instantaneous reward function R (s t, a t, s t + 1)
■■ a discount factor c ! [0, 1], where lower values place more
emphasis on immediate rewards.
In general, the policy r is a mapping from states to a probability distribution over actions r: S " p (A = a | S) . If the
MDP is episodic, i.e., the state is reset after each episode of length
T, then the sequence of states, actions, and rewards in an episode
constitutes a trajectory or rollout of the policy. Every rollout of a
policy accumulates rewards from the environment, resulting in
the return R = / Tt =-01 c t rt +1 . The goal of RL is to find an optimal policy, r * that achieves the maximum expected return from
all states:
*

	

r = argmax E [R | r] . (1)
r

State (St )
Reward (rt )
St +1

rt +1

Policy (π )
Environment

Agent
Action (at )

FIGURE 2.  The perception-action-learning loop. At time t, the agent receives state s t from the environment. The agent uses its policy to choose an action

a t . Once the action is executed, the environment transitions a step, providing the next state, s t + 1, as well as feedback in the form of a reward, rt +1 . The
agent uses knowledge of state transitions, of the form (s t , a t , s t +1, rt +1), to learn and improve its policy.

28

IEEE SIGNAL PROCESSING MAGAZINE

|

November 2017

|
Table of Contents for the Digital Edition of Signal Processing - November 2017
