# CS 530 - Lecture 10

## Algorithms for Decisions

Bernhard Firner

2026-02-24

---

## Utility and Decisions

* Let's review
* Last time we talked about utility as a metric to compare states
* Good decisions are thus actions that maximize utility

---

## Axioms of Utility Theory

* Six axioms
  * Preferences are ordered, transitive, and have continuity
  * In lotteries, preferences can be substituted, have monotonicity, and decomposability
  * See the book or slides, don't need to repeat them

---

## Why Axioms?

* If you aren't following all of the axioms, some irrational actions can occur
  * AI vending machines that give away money
  * Gachapon buyers who don't pay for more information
* Of course, we are assuming that probabilities are known or estimated

---

## Markov Decision Process

* We can usually treat our decisions as discrete
  * The results of our actions are often not fully known
  * In Markov terminology, these are stochastic state transitions
* If we have preferences for some states, then we can assign rewards
* This setup is the Markov decision process, or MDP

---

## Q-Function

* The Q function, or action-utility function, estimates utility
  * Given an action, $a$, and the current state, $s$
* The utility of a state is the utility of the best action
  * $U(s) = \underset{a}{\mathrm{max}}Q(s,a)$
* Our optimal policy selects $a$ given $s$
  * $\pi^*(s) = \underset{a}{\mathrm{argmax}}Q(s,a)$

---

## Bellman Equation

* Our goal in a MDP is to maximize the expected utility of our actions
* We will discount future rewards, * $U_i = \gamma^0R_i(a_i) + \gamma R_{i+1}(a_{i+1}) + \gamma^2R_{i+2}(a_{i+2})$
  * Because the future could be less certain or we have a finite time horizon
* The utility of a state is thus the Bellman equation:
  * $U(s) = \underset{a\in A(s)}{\mathrm{max}}\Sigma_{s'}P(s'|s,a)[R(s,a,s') + \gamma U(s')]$

---

## Grid World Example

* A robot begins in the lower left
* We want it to exit to the upper right
  * Without crossing over the tile at 4,2

</div>
<div class="col">

</div>
</div>

---

## Grid World Example

* We assign utility values to the 4,3 and 4,2 tiles
* How do we make decisions when we are in the other states?

</div>
<div class="col">

</div>
</div>

---

## MDP Algorithms

* Assigning utility values to a state space is common
* Generally, we only have reward values for the terminal states
  * For example, winning a game is +1, losing is -1
* To make decisions, we need values for everything else

---

## Value Iteration

* The algorithm we talked about last time was **value iteration**
* To make it more interesting, let us solve it with convolutions
  * As described in [Value Iteration Networks](https://proceedings.neurips.cc/paper_files/paper/2016/hash/c21002f464c5fc5bee3b98ced83963b8-Abstract.html)
* This makes our problem space differentiable
  * And that means that it will place nicely with neural networks and gradient descent

---

## Value Iteration Convolutions

* Convolutions are also a good way to understand the algorithm
* Our challenge is to solve for the maximum utility in each state
* This implies that we evaluation all actions and find the maximum
  * $U(s) = \underset{a}{\mathrm{max}}Q(s,a)$

---

## Single Step Utility

* There are four possible actions 
  * Up, down, left, right
* To make things stochastic, the robot moves at a right angle with p=0.1

---

## Starting With Up

* The reward for going up is the probability of each future state, multiply by their utility
  * so $0.1U(left) + 0.8U(up) + 0.1U(right)$
* We can encode that as the filter $[[0, 0.8, 0], [0.1, 0, 0.1], [0, 0, 0]]$
  * We take 0.8 of the utility of the upward space, and 0.1 of the left and right

---

## Movement Penalty

* We are supposed to apply a penalty of -0.04 for each action
  * This is to make the robot eventually exit
  * We can represent this as a bias of -0.04 applied to the result of each convolution

---

## Full Program

```python
import torch

known_rewards = torch.zeros((1, 1, 3, 4))
known_rewards[0, 0, 0, 3] = 1
known_rewards[0, 0, 1, 3] = -1

# The convolution represents our actions
conv = torch.nn.Conv2d(in_channels=1, out_channels=4, kernel_size=(3,3), stride=1, padding=1)

with torch.no_grad():
    # Up
    conv.weight[0, 0] = torch.tensor([[0, 0.8, 0], [0.1, 0, 0.1], [0, 0, 0]])
    # Right
    conv.weight[1, 0] = torch.tensor([[0, 0.1, 0], [0, 0, 0.8], [0, 0.1, 0]])
    # Down
    conv.weight[2, 0] = torch.tensor([[0, 0, 0], [0.1, 0, 0.1], [0, 0.8, 0]])
    # Left
    conv.weight[3, 0] = torch.tensor([[0, 0.1, 0], [0.8, 0, 0], [0, 0.1, 0]])

# The weights should then be multiplied by gamma, the discount factor.
gamma = 1

# The bias is the cost of each action, e.g. -0.04
with torch.no_grad():
    conv.bias.fill_(-0.04)

# Select the best possible next state utility
maxpool = torch.nn.MaxPool3d(kernel_size = (4,1,1))

torch.set_printoptions(precision=2, sci_mode=False)

# Starting state
state = known_rewards
for i in range(100):
    state = maxpool(conv(state.view(1, 1, 3, 4)))
    # Some rewards are fixed, including the obstacle (with 0 reward)
    state[0, 0, 0, 3] = 1
    state[0, 0, 1, 3] = -1
    state[0, 0, 1, 1] = 0
    print(f"Step {i}")
    print(state)

```

---

## Step 0

---

## Step 1

---

## Step 2

---

## Step 3

---

## Step 4

---

## Step 5

---

## Step 6

---

## Step 7

---

## Step 99

---

## Notes

* Not exactly the same as the book example
  * We didn't capture the "bouncing" effect if we hit a wall
* Captures the idea

---

## Convergence

* This converges quickly, after around 7 steps
  * The algorithm should check for updates and stop at small deltas
* Is that a guarantee?
  * Yes!

---

## Convergence Guarantee

* Value iteration is guaranteed to converge
  * Due to the [Banach fixed-point theorem](https://en.wikipedia.org/wiki/Banach_fixed-point_theorem)
* As long as either $\gamma < 1$ or we have terminal states
* This is fairly important; it means that optimal decision can be made without infinite planning

---

## Estimation

* We can stop as early as we want
  * The policy we produce will be based upon some error
  * Is that a disaster?
* After a few iterations of our convnet value iteration, our utility preferences would match the converged ones

---

## Policy Iteration

* That idea suggests another approach to MDPs
* Start with some policy, $\pi_0$
  * Calculate the expected utility using that policy
  * Look ahead one step and calculate a new policy
  * Go back to the first step

---

## Policy Iteration

* The way we estimate the next policy where this differs from value iteration
* The next policy does not come from taking the optimal action over all possible actions
* Instead, we sum the utility of all possible next states
  * This makes the equations linear, allowing for exact solutions with linear algebra solvers

---

## Nonoptimal Solutions

* It has become more common for us to seek out non-optimal solutions
  * Our information is likely imperfect anyway
* Consider value iteration using convolutions

---

## Learning Utility

* Reverse the convolution work from earlier
  * What if we know the best action, but not the state utilities
* We could train a neural network to predict utilities based upon the environment
  * Then our action policy selects the highest utility state
  * If that is non-optimal, we penalize the neural network through a loss function

---

## Utility Values

* Remember, the absolute utility values themselves don't matter
  * Just the relative values
* So we can use any estimate of $Q(a, s)$
  * It turns out that machine learning is excellent at this step

---

## Example

* We saw an example of that last lecture, where convnets estimated a solution
  * [Value Iteration Networks](https://proceedings.neurips.cc/paper_files/paper/2016/hash/c21002f464c5fc5bee3b98ced83963b8-Abstract.html)

</div>

---

## Using Utilities

* Predicted rewards/utilities are then fed into a policy
  * This can also be learned, with some temporal learning
    * For example, with reinforcement learning

</div>

---

## Result

* Works on grid worlds

</div>

---

## Where We Are

* We've talked about environments
  * And trouble with sensors and data collection
* Estimating our current state
  * Markov models in discrete environments, filtering and sensor fusion in continuous
* Utility functions, preferences, and evaluating decisions

---

## What's Next

* Machine learning is going to tie all of this together
* Applied to all parts of the AI stack
  * For perception
  * Current state estimation
  * Estimating utility