Reinforcement Learning: Optimization Problem

• Reinforcement learning increases the probability of a response reoccurring in a situation.
• Reinforcement learning strengthens an action if it leads to a satisfactory outcome or an improvement in the state of affairs.
• Researchers are interested in reinforcement learning methods for designing autonomous robotic agents and finding solutions to large-scale dynamic decision-making problems.
• Reinforcement learning is formulated as an optimization problem.
• The most important aspect of a reinforcement learning system is continuing to improve, not achieving optimal behavior.
• Reinforcement learning differs from supervised learning and unsupervised learning.

The Reinforcement Learning Problem

• Reinforcement learning involves an agent interacting with its environment over time.

• At each discrete time step t, the agent receives a representation of the environment's current state st from set S, and executes an action at from set A(st).

• The agent then receives a reward rt+1 and faces a new state st+1.

• The reward and new state are influenced by the agent's action, the state in which the action was taken, and random factors.

• The agent uses a policy to select actions, using a function π that assigns a probability to each action π(s,a) for all states and actions.

• The agent adjusts its policy to maximize the return it receives over time.

• The most commonly studied type of return is the discounted return.

• The discounted return for step t is calculated by the equation:

  

• γ∈ [0, 1) is the discount factor, which determines the present value of future rewards.

• A reinforcement learning agent adjusts its policy to maximize the expected value of the discounted return.

• If γ = 0, the agent maximizes immediate rewards.

• As γ approaches 1, the agent considers future rewards more strongly and becomes more far-sighted.

• Discounting is used because it simplifies dealing with cases where the agent and environment can interact for an unbounded number of time steps.

• Episodic problems have a finite number of steps in each learning trial, allowing γ to be set to one.

• The reinforcement learning problem is based on the theory of Markoυ decision processes (MDPs).

• In an MDP, the environment state at time t provides the same information about what will happen next as the entire history up to step t.

• A full specification of an MDP includes the probabilistic details of state transitions and rewards influenced by states and actions.

• The objective is to compute an optimal policy that maximizes the expected return from each state, which can be done using stochastic dynamic programming algorithms.

• Reinforcement learning emphasizes approximating optimal behavior during on-line behavior instead of computing optimal policies off-line with known probabilistic models.

• The objective in reinforcement learning is to allow the agent to receive as much reward as possible during its behavior, not to compute an optimal policy for all possible states.

Key Observations:

• Uncertainty plays a central role in reinforcement learning due to random fluctuations in the agent's environment and behavior.
• The reward can be any scalar signal evaluating the agent's behavior, like success, failure, or moment-by-moment evaluations, and can be combined via a weighted sum.
• The credit-assignment problem is how to distribute credit for success among the many decisions that may have been involved.
• A reinforcement learning system may forgo immediate reward to obtain more reward later, because actions influence both reward input and state transitions.
• The reward evaluates the action taken but does not directly indicate the best action.
• Reinforcement learning algorithms are selectional processes, requiring variety in the action-generation process to compare the consequences of alternative actions.
• Behavioral variety is called exploration.
• Reinforcement learning involves a balance between exploitation and exploration, where the agent has to exploit what it has learned to obtain rewards and explore new ways to learn more.

Value Functions

• Value functions are scalar functions of states or state-action pairs that indicate how good it is for the agent to be in a state or take an action in a state.

• "How good" relates to the return expected to accumulate.

• The state value function Vπ gives the value Vπ(s) of each state s, representing the return expected after visiting s, assuming actions are chosen according to policy π.

• Equation of value of state s:

  

• V*(s) is the state's optimal value and the return expected after visiting s assuming optimal actions are chosen.

• The action value Qπ(s, a) is the expected return starting from s, taking action a, and thereafter following policy π.

• Equation is action value of taking action a in state s under a policy π:

  

• Q*(s, a) is the optimal action value and taking action a in state s, and following an optimal policy.

• If V is known, optimal policies can be found by looking ahead one time step.

• The optimal action at step t is any a ∈ A(st) that maximizes rt+1 + ¥V*(st+1).

• If is known, finding optimal actions is easier.

• A greedy action is a one-step ahead maximizing action for a state value function or an action-value function.

• Value functions, Vπ and Qπ, improve behavior because of the policy improvement property.

• If an agent picks an action greedy with respect to Vπ or picks some other action

• Its performance is guaranteed to be at least as good as it would have been under π.

• The fundamental property of value functions is that they satisfy particular consistency conditions if the Markov property holds.

• Consistency condition:

  

• V* satisfies the equation for all s ∈ S:

  

• satisfies:

• Probabilistic details of how the environment responds to actions can be solved using Bellman Equations.
• Solving Bellman equations is one route to finding optimal policies.
• In many problems, there is no complete Markov model of the environment or the state set is too large.

Reinforcement Learning Based on Value Functions

• Actor-critic architecture is used in reinforcement learning to maintain both a value function and a policy.
• The agent consults its policy via an actor component and also consults a critic component which maintains the value function.
• The action is considered good/bad depending if it leads to a next state with a higher/lower value than s, both state values being estimated by the critic.
• Upon receiving the evaluation, the actor updates the policy, implementing Edward Thorndike's "Law of Effect".
• The critic updates its value function estimate.
• Barto, Sutton, and Anderson (1983) used this architecture for learning to balance a simulated pole mounted on a cart.
• The critic provides an internal reinforcement signal via changes in estimated values, offering immediate action evaluations to maximize reward over the long-term.
• This method thus relies on the policy improvement property.
• Another type of reinforcement learning algorithm uses value functions and selects actions solely by consulting its current value function estimate.
• Like actor-critic methods, this approach also relies on the policy improvement property.

Estimating Value Functions

• The simplest method for estimating the value function is to average an ensemble of returns actually observed.

• If an agent follows policy, and maintains Vπ(s), then the averages will converge to Vπ(s)

• Separates averages kept for each action converge to action values, Qπ(s, a). This is easiest in episodic problems.

• These methods are called simple Monte Carlo value estimation methods.

• TD algorithms include tabular TD(0) and estimates Vπ.

• TD(0) updates the current estimate of the value of states, V(s) using the following step:

  

• α is a positive step-size parameter.

• TD algorithms are based on the consistency condition expressed by the Bellman equations.

• The term r is the TD error, moving toward zero for every state.

• An update of this general form is called a backup.

• There are also TD(λ) algorithms, include eligibility traces and vary λ.

• Adaptive critic algorithms use forms of TD algorithms.

• Q-learning directly estimates without relying on the policy improvement property.

• The equation for Q-learning:

  

• Sarsa updates the action value differently, it is closely related to Q-learning.

• Sarsa Update:

  

• Sarsa and Q-learning have different properties.

• The TD algorithms can use eligibility traces.

• TD algorithms are closely related to dynamic programming algorithms, which also use backup operations derived from Bellman equations.

  • 2 main differences:
    • DP uses the state-transition distribution of the MDP, whereas a TD backup uses a sample from this distribution
    • DP uses multiple exhaustive “sweeps” of the MDP's state set, whereas TD algorithms operate on states as they occur.

Function Approximation

• Instead of lookup tables, store estimated values of states or state-action pairs more compactly.

Exploration

• Learning agents have to sometimes select actions that are suboptimal.
• Agents select ε-greedy actions with probability 1 – ε; selects an action at random, or by independent current value estimates.

Direct Policy Search

• It is possible to search directly in the space of policies.
• The amount of reward that a policy yields can be estimated by running the policy for some number of time steps.

Using Environment Models

• Many reinforcement learning systems take advantage of environment models.
• Sample models learn from simulations.
• Stochastic dynamic programming algorithms need distribution models.
• Reinforcement learning algorithms that use models are a form of planning.