Tile Coding.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tile Coding\n",
    "\n",
    "I try to decipher the cryptic Sutton's code, that can be found [here](http://incompleteideas.net/tiles/tiles3.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some basic lingo - **Tiling** refers to a new grid. **Tile** refers to a single element in that grid."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**IHT** (probably) stands for index-hash-table."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general, the code implementation is rather cryptic. Let's break down the algorithm though -"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* It has no boundary - it can receive any number - it's up to you to decide which numbers to give it - i.e. your **domain**.\n",
    "* It assumes tiles are done on integer level. I.e. all points between 1 and 2 are considered 1 tile. All points between 2 and 3 are a different tile. It's up to you to scale the coordinates appropriately before passing it to the method. I.e. if you want 2x2 grid between 1 and 2, you have to scale the points x2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So if your states are limited in \\[-1,1\\]x\\[-1,1\\] and you want to divide it to 10 tiles each, you need to scale it by (10/(1-(-1)))=5 for each axis. I.e. you should transform your states to \\[-5,5\\]x\\[-5,5\\] before passing them to the method."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, moving on:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The code breaks each tile to a (tiling)x(tiling) parts. \n",
    "\n",
    "* The tiling are all-encompassing, i.e. they are shifted, but are considered also before and after. This is a bit confusing. Here is how the 2 2x2 tilings actually look like:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![encompass](encompass.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So the point marked in a yellow star would have a corresponding (2,2) for the 1st tiling, and (3,3) for the 2nd tiling. (indices start at 1). \n",
    "**Since we can ignore anything outside the red square (which is our domain, anything outside it we don't care about), there will be exactly 16 states, or (2x2)x(2x2) for (tiling^2)x(tiles^2).**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Also, given a certain tile, say the one from 0 to 1, this is where it will start the different tiling divisions, given 4 tiling's: each new tiling will be shifted by -0.25 on the x axis, and -0.75 on the y axis:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![tiling](tilings.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "i.e. if 1 is [0,1]x[0,1] - 2 is [-0.25,0.75]x[-0.75,0.25] etc.\n",
    "\n",
    "I don't know why Sutton did this, that the y jumps like this - I think it could have worked perfectly well if the y would jump like the x, and it would make the code simpler. If the end goal is just to divide each tile to tiling x tiling, it doesn't matter in what order you do it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Moving on - "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Regarding the hash table - It stores the different indices in a first-seen order. I.e. if you give it (3,3) and then (1,1) or (1,1) and then (3,3) it will store the indices as (0,1) and (2,3) in either case.\n",
    "* The size you should give it, should be equal to at-least (tiling^2)x(tiles^2) - since this is how many states you will have for your given domain. \n",
    "* Tiles return the different indices, and not the actual coordinates - this abstracts away your need to care about the actual coordinates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}