1 Reinforcement Learning and Evaluating Hypotheses

MODULE -5
Reinforcement Learning and Evaluating Hypotheses

Introduction
 Consider building a learning robot. The robot, or agent, has a set of sensors to observe the
state ofits environment, and a set of actions it can perform to alter this state.
 Its task is to learn a control strategy, or policy, for choosing actions that achieve its goals.
 The goals of the agent can be defined by a reward function that assigns a numerical value
to eachdistinct action the agent may take from each distinct state.
 This reward function may be built into the robot, or known only to an external
teacher whoprovides the reward value for each action performed by the robot.
 The task of the robot is to perform sequences of actions, observe their consequences, and
learn acontrol policy.
 The control policy is one that, from any initial state, chooses actions that maximize the
rewardaccumulated over time by the agent.

Example:
 A mobile robot may have sensors such as a camera and sonars, and actions such as "move
forward" and "turn."
 The robot may have a goal of docking onto its battery charger whenever its battery level is low.
 The goal of docking to the battery charger can be captured by assigning a positive reward (Eg.,
+100) to state-action transitions that immediately result in a connection to the charger
and areward of zero to every other state-action transition.

Reinforcement Learning Problem

 An agent interacting with its environment. The agent exists in an environment described by
some set of possible states S.
 Agent perform any of a set of possible actions A. Each time it performs an action a, in some
state stthe agent receives a real-valued reward r, that indicates the immediate value of this
state-action transition. This produces a sequence of states si, actions ai, and immediate
rewards ri as shown in the figure.
 The agent's task is to learn a control policy, 𝝅: S → A, that maximizes the expected sum
of theserewards, with future rewards discounted exponentially by their delay.

Nayana M Ass. Prof. SVIT

2 Reinforcement Learning and Evaluating Hypotheses

Reinforcement learning problem characteristics

1. Delayed reward: The task of the agent is to learn a target function 𝜋 that maps from the current
state s to the optimal action a = 𝜋 (s). In reinforcement learning, training information is not
available in (s, 𝜋 (s)). Instead, the trainer provides only a sequence of immediate reward values as
the agent executes its sequence of actions. The agent, therefore, faces the problem of temporal
credit assignment: determining which of the actions in its sequence are to be credited with
producing the eventualrewards.

2. Exploration: In reinforcement learning, the agent influences the distribution of training

examples by the action sequence it chooses. This raises the question of which experimentation
strategy produces most effective learning. The learner faces a trade-off in choosing whether to
favor exploration of unknown states and actions, or exploitation of states and actions that it has
already learned will yield high reward.

3. Partially observable states: The agent's sensors can perceive the entire state of the
environment at each time step, in many practical situations sensors provide only partial
information. In such cases, the agent needs to consider its previous observations together with its
current sensor data when choosing actions, and the best policy may be one that chooses actions
specifically to improve the observability of the environment.

4. Life-long learning: Robot requires to learn several related tasks within the same environment,
using the same sensors. For example, a mobile robot may need to learn how to dock on its battery
charger, how to navigate through narrow corridors, and how to pick up output from laser printers.
This setting raises the possibility of using previously obtained experience or knowledge to reduce
sample complexitywhen learning new tasks.

Learning Task
 Consider Markov decision process (MDP) where the agent can perceive a set S of distinct
states ofits environment and has a set A of actions that it can perform.
 At each discrete time step t, the agent senses the current state st, chooses a current action at,
andperforms it.

Nayana M Ass. Prof SVIT

3 Reinforcement Learning and Evaluating Hypotheses

 The environment responds by giving the agent a reward rt = r(st, at) and by producing the
succeeding state st+l = δ(st, at). Here the functions δ(st, at) and r(st, at) depend only on the
currentstate and action, and not on earlier states or actions.

The task of the agent is to learn a policy, 𝝅: S → A, for selecting its next action a, based on
the currentobserved state st; that is, (st) = at.

How shall we specify precisely which policy π we would like the agent to learn?

1. One approach is to require the policy that produces the greatest possible cumulative reward
for therobot over time.
 To state this requirement more precisely, define the cumulative value Vπ (st) achieved by
followingan arbitrary policy π from an arbitrary initial state st as follows:

 Where, the sequence of rewards rt+i is generated by beginning at state st and by repeatedly
using the policy π to select actions.
 Here 0 ≤ γ ≤ 1 is a constant that determines the relative value of delayed versus immediate
rewards. if we set γ = 0, only the immediate reward is considered. As we set γ closer to 1,
future rewards are given greater emphasis relative to the immediate reward.
 The quantity Vπ (st) is called the discounted cumulative reward achieved by policy π from
initial state s. It is reasonable to discount future rewards relative to immediate rewards
because, in manycases, we prefer to obtain the reward sooner rather than later.

2. Other definitions of total reward is finite horizon reward,

Considers the undiscounted sum of rewards over a finite number h of steps

3. Another approach is average reward

Considers the average reward per time step over the entire lifetime of the agent.

We require that the agent learn a policy π that maximizes Vπ (st) for all states s. such a policy
is calledan optimal policy and denote it by π*

Nayana M Ass. Prof. SVIT

4 Reinforcement Learning and Evaluating Hypotheses

Refer the value function Vπ*(s) an optimal policy as V*(s). V*(s) gives the maximum
discountedcumulative reward that the agent can obtain starting from state s.

Example:
A simple grid-world environment is depicted in the diagram

 The six grid squares in this diagram represent six possible states, or locations, for the agent.
 Each arrow in the diagram represents a possible action the agent can take to move from one
stateto another.
 The number associated with each arrow represents the immediate reward r(s, a) the agent
receives if it executes the corresponding state-action transition
 The immediate reward in this environment is defined to be zero for all state-action transitions
except for those leading into the state labelled G. The state G as the goal state, and the agent
can receive reward by entering this state.

Once the states, actions, and immediate rewards are defined, choose a value for the discount
factor γ,determine the optimal policy π * and its value function V*(s).

Let’s choose γ = 0.9. The diagram at the bottom of the figure shows one optimal policy for this setting.

Nayana M Ass. Prof SVIT

5 Reinforcement Learning and Evaluating Hypotheses

Values of V*(s) and Q(s, a) follow from r(s, a), and the discount factor γ = 0.9. An
optimal policy,corresponding to actions with maximal Q values, is also shown.

The discounted future reward from the bottom centre state is

0+ γ 100+ γ2 0+ γ3 0+... = 90
Q LEARNING
How can an agent learn an optimal policy π * for an arbitrary environment?
The training information available to the learner is the sequence of immediate rewards
r(si,ai)for i = 0, 1,2, Given this kind of training information it is easier to learn a
numerical evaluation
function defined over states and actions, then implement the optimal policy in terms of this
evaluationfunction.

What evaluation function should the agent attempt to learn?

One obvious choice is V*. The agent should prefer state sl over state s2 whenever V*(sl) >
V*(s2),because the cumulative future reward will be greater from sl
The optimal action in state s is the action a that maximizes the sum of the immediate reward r(s,
a) plusthe value V* of the immediate successor state, discounted by γ.

The Q Function
The value of Evaluation function Q(s, a) is the reward received immediately upon
executingaction a from state s, plus the value (discounted by γ ) of following the optimal
policy thereafter

Nayana M Ass. Prof. SVIT

6 Reinforcement Learning and Evaluating Hypotheses

Rewrite Equation (3) in terms of Q(s, a) as

Equation (5) makes clear, it need only consider each available action a in its current state s and
choosethe action that maximizes Q(s, a).

An Algorithm for Learning Q

 Learning the Q function corresponds to learning the optimal policy.
 The key problem is finding a reliable way to estimate training values for Q, given only a
sequence of immediate rewards r spread out over time. This can be accomplished through
iterativeapproximation

Rewriting Equation

Q learning algorithm:

 Q learning algorithm assuming deterministic rewards and actions. The discount factor γ may
be anyconstant such that 0 ≤ γ < 1

Nayana M Ass. Prof SVIT

7 Reinforcement Learning and Evaluating Hypotheses

 𝑄̂ to refer to the learner's estimate, or hypothesis, of the actual Q function

An Illustrative Example

 To illustrate the operation of the Q learning algorithm, consider a single action taken by an
agent,and the corresponding refinement to 𝑄̂ shown in below figure

 The agent moves one cell to the right in its grid world and receives an immediate reward of
zero forthis transition.
 Apply the training rule of Equation

to refine its estimate Q for the state-action transition it just executed.

 According to the training rule, the new 𝑄̂ estimate for this transition is the sum of the
receivedreward (zero) and the highest 𝑄̂ value associated with the resulting state (100),
discounted by γ (.9).

Convergence
Will the Q Learning Algorithm converge toward a Q equal to the true Q function?
Yes, under certain conditions.
1. Assume the system is a deterministic MDP.
2. Assume the immediate reward values are bounded; that is, there exists some positive constant
c suchthat for all states s and actions a, | r(s, a)| < c
3. Assume the agent selects actions in such a fashion that it visits every possible state-
action pairinfinitely often

Nayana M Ass. Prof. SVIT

8 Reinforcement Learning and Evaluating Hypotheses

Nayana M Ass. Prof SVIT

9 Reinforcement Learning and Evaluating Hypotheses

Experimentation Strategies
The Q learning algorithm does not specify how actions are chosen by the agent.
 One obvious strategy would be for the agent in state s to select the action a that maximizes
𝑄̂(s, a),thereby exploiting its current approximation 𝑄̂.
 However, with this strategy the agent runs the risk that it will overcommit to actions that
arefound during early training to have high Q values, while failing to explore other actions
that have even higher values.
 For this reason, Q learning uses a probabilistic approach to selecting actions. Actions with
higher 𝑄̂ values are assigned higher probabilities, but every action is assigned a nonzero
probability.
 One way to assign such probabilities is

 Where, P(ai |s) is the probability of selecting action ai, given that the agent is in state s, and
k > 0 isa constant that determines how strongly the selection favors actions with high 𝑄̂ values

Evaluating Hypotheses
Motivation
It is important to evaluate the performance of learned hypotheses as precisely as possible.
 One reason is simply to understand whether to use the hypothesis.
 A second reason is that evaluating hypotheses is an integral component of many
learningmethods.

Two key difficulties arise while learning a hypothesis and estimating its future accuracy
given only alimited set of data:

1. Bias in the estimate. The observed accuracy of the learned hypothesis over the training
examples is often a poor estimator of its accuracy over future examples. Because the learned
hypothesis was derived from these examples, they will typically provide an optimistically biased
estimate of hypothesis accuracy over future examples. This is especially likely when the learner
considers a very rich hypothesisspace, enabling it to overfit the training examples. To obtain an

Nayana M Ass. Prof. SVIT

10 Reinforcement Learning and Evaluating Hypotheses

unbiased estimate of future accuracy, test the hypothesis on some set of test examples chosen

Nayana M Ass. Prof SVIT

11 Reinforcement Learning and Evaluating Hypotheses

independently of the training examples and the hypothesis.

2. Variance in the estimate. Even if the hypothesis accuracy is measured over an unbiased set of
test examples independent of the training examples, the measured accuracy can still vary from the
true accuracy, depending on the makeup of the particular set of test examples. The smaller the set
of test examples, the greater the expected variance.

Estimating Hypothesis Accuracy

Sample Error –
The sample error of a hypothesis with respect to some sample S of instances drawn from
X is thefraction of S that it misclassifies.

Definition: The sample error (errors(h)) of hypothesis h with respect to target function f
and datasample S is

Where n is the number of examples in S, and the quantity δ(f(x), h(x)) is 1 if f (x) ≠
h(x), and 0otherwise.
True Error –
The true error of a hypothesis is the probability that it will misclassify a single
randomly drawninstance from the distribution D.
Definition: The true error (errorD (h)) of hypothesis h with respect to target function f and
distribution D, is the probability that h will misclassify an instance drawn at random
according to D.

Confidence Intervals for Discrete-Valued Hypotheses

Suppose we wish to estimate the true error for some discrete valued hypothesis h, based on its
observed sample error over a sample S, where
 The sample S contains n examples drawn independent of one another, and independent
of h,according to the probability distribution D
 n ≥ 30
 Hypothesis h commits r errors over these n examples (i.e., errors (h) = r/n).

Under these conditions, statistical theory allows to make the following assertions:
1. Given no other information, the most probable value of errorD (h) is errors(h)
2. With approximately 95% probability, the true error errorD (h) lies in the interval

Nayana M Ass. Prof. SVIT

12 Reinforcement Learning and Evaluating Hypotheses

Example:
Suppose the data sample S contains n = 40 examples and that hypothesis h commits r = 12 errors
overthis data.
 The sample error is errors(h) = r/n = 12/40 = 0.30
 Given no other information, true error is errorD (h) = errors(h), i.e., errorD (h) = 0.30
 With the 95% confidence interval estimate for errorD (h).

= 0.30 ± (1.96 * 0.07)

= 0.30 ± 0.14
3. A different constant, ZN, is used to calculate the N% confidence interval. The general
expression forapproximate N% confidence intervals for errorD (h) is

Where,

The above equation describes how to calculate the confidence intervals, or error bars, for
estimates oferrorD (h) that are based on errors(h)

Example:
Suppose the data sample S contains n = 40 examples and that hypothesis h commits r = 12 errors
overthis data.
 The sample error is errors(h) = r/n = 12/40 = 0.30
 With the 68% confidence interval estimate for errorD (h).

Nayana M Ass. Prof SVIT

13 Reinforcement Learning and Evaluating Hypotheses

= 0.30 ± (1.00 * 0.07)

= 0.30 ± 0.07

Basics of Sampling Theory

Error Estimation and Estimating Binomial Proportions
 Collect a random sample S of n independently drawn instances from the distribution D, and
then measure the sample error errors(h). Repeat this experiment many times, each time
drawing a different random sample Si of size n, we would expect to observe different values
for the various errorsi(h), depending on random differences in the makeup of the various Si.
We say that errorsi(h), the outcome of the ith such experiment, is a random variable.
 Imagine that we were to run k random experiments, measuring the random variables
errors1(h), errors2(h) . . . errorssk(h) and plotted a histogram displaying the frequency with
which each possible error value is observed.
 As k grows, the histogram would approach a particular probability distribution called the
Binomial distribution which is shown in below figure.

A Binomial distribution is defined by the probability function

If the random variable X follows a Binomial distribution, then:

 The probability Pr(X = r) that X will take on the value r is given by P(r)

Nayana M Ass. Prof. SVIT

14 Reinforcement Learning and Evaluating Hypotheses

The Binomial Distribution

Consider the following problem for better understanding of Binomial Distribution
 Given a worn and bent coin and estimate the probability that the coin will turn up heads
whentossed.
 Unknown probability of heads p. Toss the coin n times and record the number of times r
that itturns up heads.
Estimate of p = r / n
 If the experiment were rerun, generating a new set of n coin tosses, we might expect the
number of heads r to vary somewhat from the value measured in the first experiment,
yieldinga somewhat different estimate for p.
 The Binomial distribution describes for each possible value of r (i.e., from 0 to n), the
probabilityof observing exactly r heads given a sample of n independent tosses of a coin
whose true probability of heads is p.

The general setting to which the Binomial distribution applies is:

1. There is a base experiment (e.g., toss of the coin) whose outcome can be described by a random
variable ‘Y’. The random variable Y can take on two possible values (e.g., Y = 1 if heads, Y = 0
if tails).
2. The probability that Y = 1 on any single trial of the base experiment is given by some constant
p, independent of the outcome of any other experiment. The probability that Y = 0 is therefore (1
- p). Typically, p is not known in advance, and the problem is to estimate it.
3. A series of n independent trials of the underlying experiment is performed (e.g., n independent
coin tosses), producing the sequence of independent, identically distributed random variables Y1,
Y2, . . ., Yn. Let R denote the number of trials for which Yi = 1 in this series of n experiments

4. The probability that the random variable R will take on a specific value r (e.g., the
probability ofobserving exactly r heads) is given by the Binomial distribution

Nayana M Ass. Prof SVIT

15 Reinforcement Learning and Evaluating Hypotheses

Mean, Variance and Standard Deviation

The Mean (expected value) is the average of the values taken on by repeatedly sampling the
randomvariable

Definition: Consider a random variable Y that takes on the possible values y1, . . . yn. The
expectedvalue (Mean) of Y, E[Y], is

The Variance captures how far the random variable is expected to vary from its mean value.
Definition: The variance of a random variable Y, Var[Y], is

The variance describes the expected squared error in using a single observation of Y to
estimate itsmean E[Y].

The square root of the variance is called the standard deviation of Y, denoted σy

Definition: The standard deviation of a random variable Y, σy, is

In case the random variable Y is governed by a Binomial distribution, then the Mean, Variance
and standarddeviation are given by

[Link]. Estimators, Bias, and Variance

Let us describe errors(h) and errorD(h) using the terms in Equation (1) defining the
Binomialdistribution. We then have

Where,

Nayana M Ass. Prof. SVIT

16 Reinforcement Learning and Evaluating Hypotheses

 n is the number of instances in the sample S,

 r is the number of instances from S misclassified by h

 p is the probability of misclassifying a single instance drawn from D

 Estimator:

errors(h) an estimator for the true error errorD(h): An estimator is any random variable
used toestimate some parameter of the underlying population from which the sample is
drawn
 Estimation bias: is the difference between the expected value of the estimator and the true
value ofthe parameter.

Definition: The estimation bias of an estimator Y for an arbitrary parameter p is

Nayana M Ass. Prof SVIT

17 Reinforcement Learning and Evaluating Hypotheses

Nayana M Ass. Prof. SVIT