Coarse Coding, such as Tile Coding, is a nice way of storing a model of the environment linear in nature or have ordinal characteristics (for instance, alphabets are ordinal since it can be ordered: A < B < C, …). The image above illustrates how Coarse Coding may be utilized. a) Narrow Generalization is for problem space where precision over backup speed (samples have to be taken for neighbor values to propagate). b) Broad Generalization is for problem space where generalization can be taken advantage of, making value propagation from neighbors faster.

The problem often occurs if our Course Coding model is too fine we want to “Broaden” our model. Before we begin, I’ll discuss a real-world problem I encountered recently.

In one of a project with a client, we are given thousands of metrics and ask to solve the following problem:

Given a pattern in a metric, what patterns in other metric entails it. For instance, given a pattern in metric M1 what pattern in other metrics are a culprit or causes it.

In our project, one of the patterns of interest is a rising web response time metric, and we are asked what entails/causes it? With a little feature engineering, we are able to linearize metrics. By running this through a program that utilizes my RL library, DB server response time was found as one of the culprits. These patterns are given below.

What the program did is basically create a model of the system so that if the DB server response time pattern does occur again, we know that it will entail rising response time. A problem arises, it is obvious that DB response time doesn’t have to follow the exact pattern above to entail web response time to rise. That is DB response time just have to be elevated around 40-50ms response time for a problem to occur. That is why we want to generalize our model stored in Coarse Coding (specifically Tile Coding).

Solution (Tile Coding)

Although this solution is only for Tile Coding, the general idea applies to other types of Coarse Coding. So in our metric above, we want to generalize it to:

Web Response Time vs DB Response Time (Broad)

Note on how the bumps are “smoothed out”. This should now give us a better model for this problem. So how do we generalize Tile Codes?

To begin, let us first review a simplified version of Tile Code where it stores a 2D state-action space (1D state and 1D action). Suppose it is stored in the following tile (we will ignore multiple tiling to simplify this further):

Suppose actions are represented by the x-axis while the states are represented by the y-axis. Generalizing would mean storing the values stored in this grid to the following “Broader Grid”:

Each square in Broad Course Code covers many vertexes in the original Course Code. The idea then is each vertex in Broad Coarse Code have a value is the weighted average of all the covered vertex in the original Course Code. This is better illustrated visually here:

Let green grid represent the original Tile Code grid.
Let the red grid represent our wanted Broad Tile Code grid.
Blue dot is one of the vertex (storage of state-action value) in our new Broad Tile Code grid.

So for the value in the vertex represented by the blue dot, it will be the weighted average of all the green vertex that is under the 4 red squares it sits on. (If vertex is at the side, then the vertex will be sitting on two squares whilst if it is in corner then it will be sitting on just one square). The weights would be the cartesian distance between a green vertex and the blue vertex. The weighted average can easily be done by the following formula:

Conclusion

Here we assume that the Tile Coding did not do any hashing. This is an equivalent of using the TileCodeCorrect class in my real library. Utilizing something with hashing shouldn’t be that big of a deal since the same representation of grids above still holds except that vertex are in “superposition”, in which a vertex is utilized by more than one state-action pair. More sophisticated methods are also needed for “nonconventional tiles”: