Action-Value Functions in Scheduling Agents
Sarsa supplies the learning method for the DRAM scheduling agent.
From State to Learned Decision
A DRAM scheduling agent repeatedly chooses actions while the system state changes. In this design, Sarsa provides the learning method. The agent does not rely on a fixed, hand-written scheduling rule. Instead, it learns an action-value function: an estimate of how useful an available action is in a represented state, based on the learning process.
The Sarsa Learning Loop
The scheduling agent begins with a represented state and a selected action. The system then moves to a subsequent state and produces a reward associated with the result of that decision. Sarsa uses the sequence of state, action, reward, next state, and next action to improve the action-value estimate. The important result is that the value estimate is updated from experience rather than being permanently specified by a hand-written rule.
This flow is a learning-agent pipeline, not a complete DRAM hardware timing diagram. The source identifies the state features, learned action-value function, approximation method, and exploration setting, but it does not specify particular DRAM commands or a detailed timing sequence.
Six-Feature State Representation
Each scheduling state is represented using six integer-valued features. Together, the six integers form the input description that the agent uses when estimating action values. The source does not identify what the individual features mean. Therefore, they should be treated as six positions in the state representation rather than assumed to describe a particular queue, bank, row, or timing field.
Reading an abstract state
Suppose a learner writes one state as the six-integer vector [2, 0, 4, 1, 3, 5]. What can be concluded from this representation?
Count the features: There are six integer positions, so the representation has the required six-feature structure.
Keep the positions abstract: The values can be used as the state representation, but the source does not say that position 1 is a queue field, position 2 is a bank field, or that any other position has a named DRAM meaning.
Use the state for learning: The complete six-integer representation is supplied to the action-value approximation process when the agent evaluates scheduling actions.
The vector is an illustrative six-feature state representation. Its individual feature meanings cannot be inferred from the source.
Approximation Through Tiling
The agent must represent action values over states, but the described design does not present this representation as a fixed table of every possible state and action combination. Instead, it uses linear function approximation implemented by tiling coding with hashing. Tiling coding transforms the state representation into tile activations, and hashing maps those activations into the storage structure used for the approximate action values.
| Part of the approximation | Source-stated detail | Role in the system |
|---|---|---|
| Tiling count | 32 tilings | Provides the tiling-coding structure used to represent the state for approximation |
| Values in each tiling | 256 action values | Stores the action-value data associated with each tiling |
| Value format | 16-bit fixed-point | Specifies the representation format of each stored action value |
| Mapping method | Hashing | Maps tile activations into the stated storage structure |
The storage details specified for the tiling-coding implementation
The practical meaning of linear approximation is that the agent obtains an approximate action-value estimate from the encoded state representation and learned stored values, rather than treating every possible state as a separately listed exact entry. The source specifies the tiling and storage arrangement, but it does not provide a numerical update equation or a detailed hash-function design.
Exploration While Learning
Exploration is part of the control process because the agent must choose scheduling actions while its action-value function is still being learned. The system uses epsilon-greedy exploration: at a decision point, epsilon represents the probability of choosing a random action, while the remaining probability is associated with choosing the currently highest-valued action. This lets the agent balance trying actions with using its current value estimates.
Interpreting epsilon-greedy choice
At one decision point, assume epsilon has been configured to a value chosen by the system designer. What are the two possible types of choice?
Exploration branch: With probability epsilon, the agent chooses a random action so that it can continue gathering experience beyond its current preferred choice.
Current-best branch: With the remaining probability, the agent chooses the action that currently has the highest estimated value.
Learning connection: The selected action becomes part of the Sarsa experience sequence used to improve the action-value function.
Epsilon controls the balance between random action selection and following the current highest-valued action. The source does not specify its numeric setting.
Mistakes in Reading the Design
Treating Sarsa as the action-value function
Sarsa supplies the learning method. The action-value function is what the scheduling agent learns.
Fix:
Describe Sarsa as the algorithm and the action-value function as the learned estimate used for scheduling decisions.Assigning undocumented meanings to the six features
The source states only that the state has six integer-valued features. It does not identify their meanings.
Fix:
Refer to the features by position or as abstract integer-valued components unless a separate source defines their meanings.Confusing tiling coding with a complete hardware timing diagram
The source presents tiling coding with hashing as the approximation implementation. It explicitly does not provide a detailed DRAM timing sequence.
Fix:
Read the tilings as part of the state-to-value representation pipeline.Inventing a numeric epsilon
The source identifies epsilon-greedy exploration but does not provide a numeric epsilon setting.
Fix:
Explain the two epsilon-greedy branches without claiming an undocumented numeric configuration.Assuming the approximation stores every possible state exactly
The described design uses linear function approximation through tiling coding with hashing.
Fix:
Explain that the state is encoded through tiles and mapped into the specified hashed storage structure.
Check Your Understanding
Explain the complete chain for this scheduling agent in five linked statements: what Sarsa provides, what the agent learns, how a state is represented, how the learned function is approximated, and how exploration affects action selection.
Hints
- Begin with Sarsa as the learning method.
- State that the learned object is an action-value function.
- Mention six integer-valued features for each state.
- Include linear function approximation through tiling coding with hashing.
- State the two epsilon-greedy choices and note that the numeric epsilon is not specified.
A diagram labels six state features as queue, bank, row, timing, request type, and priority. Based only on the source pack, should you accept those labels as documented facts? Explain why or why not.
Hints
- Separate the fact that there are six integer-valued features from the meanings of those features.
- Identify what the source explicitly leaves unspecified.
Key Takeaways
- Sarsa supplies the learning method for the DRAM scheduling agent.
- The agent learns an action-value function rather than using only a fixed hand-written scheduling rule.
- Each scheduling state is represented by six integer-valued features, whose individual meanings are not specified in the source.
- Linear function approximation is implemented through tiling coding with hashing, using 32 tilings and 256 16-bit fixed-point action values in each tiling.
- Epsilon-greedy exploration balances random action selection with choosing the currently highest-valued action, but the source does not specify a numeric epsilon.
Key Takeaways
- Sarsa is the learning method used by the scheduling agent.
- The learned object is an action-value function that estimates the usefulness of scheduling actions from represented states.
- A state contains six integer-valued features, but the source does not define the meaning of each feature.
- Tiling coding with hashing provides the linear function approximation, with 32 tilings and 256 16-bit fixed-point action values per tiling.
- Epsilon-greedy exploration chooses between random actions and the current highest-valued action; no numeric epsilon is given.