Stanford AA228/CS238 Decision Making Under Uncertainty I Policy Gradient Estimation & Optimization

Introduction and Parameterized Policies

• The proposal for the project should be a sequential decision problem, and if there's uncertainty, it's recommended to come by office hours or post on Ed for clarification (27s).
• A policy, denoted as π, is a function that tells us what action to take based on the state we're in, and it can be used to control the temperature in a building by turning on the heat or AC (1m15s).
• The policy might look like a table with associated actions for every possible temperature, but storing such a policy wouldn't be possible for large or continuous state spaces (2m13s).
• To address this issue, policies can be parameterized using parameters θ, and an example of a parameterized policy for temperature control is given using two parameters θ1 and θ2 (2m24s).

Utility and Gradient Optimization

• The utility of the policy, denoted as U(θ), is the thing that's generally interested in optimizing, and many optimization methods rely on the gradient of θ (3m16s).
• The gradient of θ, denoted as ∇θ, is a vector of partial derivatives, one for each parameter θi, and it's used to estimate the gradient of the utility function (3m51s).
• The lecture will cover a few different options for estimating the gradient of θ, and it's noted that this portion of the lecture is calculus-heavy (4m27s).

Finite Differences Method for Gradient Estimation

• The first method for estimating the gradient of a function is finite differences, which involves computing the slope between two points that are a small distance apart, denoted as Delta, to estimate the derivative at a point of interest (4m56s).
• In the multivariable case, the finite difference method is used to estimate the gradient of U(θ) by computing U(θ + Δe) - U(θ) / Δ, where e is a standard basis vector, and repeating this process for each parameter θ (6m8s).
• The standard basis vector e has a one in the position corresponding to the parameter being estimated and zeros elsewhere, allowing the method to estimate the gradient of U(θ) around a point (6m50s).
• The finite difference method can be impacted by the variance of U(θ), which may require a large number of rollouts to obtain a good estimate, and techniques can be used to mitigate this variance (7m46s).
• The parameters θ are the parameters of the parameterization, and the first-order approximation may not always work for high-dimensional cases where the parameters are on different scales (8m11s).

Regression Gradient Method for Gradient Estimation

• The next method discussed is the regression gradient, which involves collecting data points and fitting a regression line to estimate the gradient of U(θ) around a point (9m0s).
• The regression gradient method collects data points in the neighborhood of θ and fits a regression line to estimate the gradient at that point (10m38s).
• A matrix called Delta Theta is created for perturbation of each parameter, with dimensions M by N, where M is the number of perturbations and N is the number of parameters (10m42s).
• The number of perturbations is chosen empirically, with a common rule of thumb being to have double the number of parameters as the number of perturbations, but this can be based on computational constraints or expert knowledge (11m21s).
• The perturbations are obtained by randomly sampling from a normal distribution, which works well empirically, and these samples are normalized (11m48s).
• The perturbations can be visualized as points along the surface of a sphere, with each point representing a change in Theta (12m10s).
• When randomly sampling around the point Theta, the line is found by collecting data points of differences from the original Theta and differences from the original U of Theta, and then using a regression method to fit the line (12m42s).
• The method of sampling on the sphere involves sampling from a normal distribution and then normalizing the samples, so that all points are at a distance of one from the original value (13m36s).
• The same set of perturbations is applied to all coordinates, which gives the M by N matrix (14m31s).
• The random points are called perturbations, and the perturbation is the change applied to Theta (14m53s).
• The data set of points for Theta is built by applying the perturbations and computing the differences in U of Theta (15m21s).
• The computation of Delta U involves using rollouts, such as Monte Carlo simulation, to find the difference in U of Theta plus Delta Theta and U of Theta for each parameter (15m29s).
• The gradient of U of theta is estimated by fitting a line between Delta Theta and Delta U, where Delta Theta and Delta U come from policy rollouts (16m17s).
• The gradient U of theta is approximately equal to Delta Theta times the pseudo-inverse of Delta U, where the pseudo-inverse is used instead of the regular inverse because Delta Theta is not guaranteed to be invertible (16m44s).
• The pseudo-inverse of a matrix X is equivalent to the inverse of X transpose X times X transpose, which allows for the inversion of a non-square matrix (17m19s).
• The dimensions of Delta Theta and Delta U are m by 1, where m is the number of perturbations, and it is important to have an equal number of perturbations of theta and U (18m15s).
• The perturbations are sampled from an n-dimensional normal distribution, and it is not necessary to do this for every single theta since all parameters are moved in each perturbation (19m1s).

Likelihood Ratio Method for Gradient Estimation

• The likelihood ratio method is used to compute the gradient of U of theta, which involves using an analytical form of U of theta that includes an integral over all possible trajectories (19m30s).
• The integral includes the probability of a trajectory given theta, the return for that trajectory, and the discount over the entire sequence (20m14s).
• The return for a trajectory can be formulated using the Bellman optimality equation, which allows for a discount over the entire sequence (21m33s).
• The return for a trajectory is determined, and the likelihood of the trajectory is determined by the policy parameterized by Theta, which tells us what action to take based on a state (21m45s).
• The policy is determining how likely a trajectory is, and the goal is to optimize the utility of the policy by finding the gradient of the utility (23m1s).
• The process of optimizing the policy is similar to optimizing the parameters of a neural network by finding the gradient of the loss and slowly changing the parameters to improve the utility (23m42s).
• The policy determines the likelihood of a trajectory, and the goal is to take the analytical expression and get an expression for the gradient of U of theta from it (24m16s).
• The first step in finding the gradient of U of theta is to take the gradient of both sides of the expression and move the gradient inside the integral (24m33s).
• Multiplying the expression inside the integral by one allows it to be written in a way that can be simplified, and it can be written as the expectation over a certain expression (25m44s).
• The expression can be written as the expectation over tow of G Theta P Theta of to over P Theta of to R of to D to, which is a form of expectation (26m19s).
• The log derivative trick, mentioned in chapter 10.5, allows the expression to be written in a certain way, but it will not be derived today (27m52s).
• The expectation form of the gradient U of theta is expressed as an expectation, providing a relationship that can be used to estimate the gradient.
• To estimate the gradient, it is necessary to find the gradient with respect to Theta of the log of P Theta of to, which depends on the type of policy used, either stochastic or deterministic.
• A deterministic policy always returns the same action for a given state, whereas a stochastic policy provides a distribution over actions for a given state.
• For a stochastic policy, Pi Theta of a specific action given a state is the probability of taking that action from that state.
• The lecture will focus on the stochastic case, which is easier to compute and provides an interesting insight into why it is preferred.
• To find the gradient with respect to Theta log P Theta of to for a stochastic policy, it is necessary to consider a sequence of states, actions, and rewards or returns up to a certain time horizon.
• The probability of a trajectory to is calculated as the product of the probability of the initial state, the transition probabilities, and the likelihood of each action according to the policy.
• The policy does not affect the initial state, which is sampled from a distribution independent of the policy.
• The transition probabilities and the likelihood of each action are used to calculate the likelihood of the next state in the trajectory.
• The product of these probabilities gives the likelihood of the trajectory to according to the policy parameterized by Theta.
• The likelihood of a trajectory is calculated by multiplying the probability of the first state by the product of the policy and transition probabilities for each state in the sequence, resulting in the overall likelihood of the trajectory (34m39s).
• The product involves the policy and transition probabilities for each state in the sequence, with the superscripts on the states representing the time step (35m17s).
• The product starts from the first state, not the second, as it represents the transition from the first state to the second (35m40s).
• The expression for the likelihood of the trajectory is then taken to the log, converting the product into a summation (36m36s).
• The log of the probability of the first state and the summation of the log of the policy and transition probabilities for each state in the sequence are the components of the log likelihood expression (37m17s).
• Taking the gradient of the log likelihood with respect to the policy parameter results in the terms that are not dependent on the policy parameter dropping out (38m19s).
• The resulting expression is a summation that provides another option for estimating the log likelihood (38m52s).
• The terms that drop out are those that do not have any dependence on the policy parameter, similar to taking a derivative with respect to a variable that is not present in the expression (39m12s).
• The correct range for the summation is from K=1 to D-1, where D is the depth of the trajectory, as going beyond D-1 would involve states that are not part of the current trajectory (39m44s).
• When taking the derivative of theta, we end up looking at the state-action pair, and the last term is only going to D minus one, but for the second summation, it can still go to D because the transition at the D level doesn't matter (41m29s).
• The counter K is stopping at D, so we would do K from one to D, including the first state and action, and then the second, and so on, all the way to D in the summation (43m7s).
• To find the expectation, we need to consider multiple trajectories, and in practice, it's hard to iterate over all of them, so we would be sampling trajectories, and we can use different characteristics or methods to sample (43m55s).
• The goal is to calculate the gradient of the utility function, and there are three different methods to estimate the gradient, including finite differences, to optimize the parameters of our policy Theta with respect to utility (45m14s).
• We're assuming we're not able to compute the gradient directly, and these methods are possible options to estimate the gradient of the utility function (45m27s).
• The methods discussed are used to estimate the gradient of the utility function so that we can optimize the parameters of our policy, and Kiana will discuss what to do with these estimates (42m53s).