Why do my rewards fall using tabular Q-learning as I perform more episodes?
The problem here is likely related to the state approximations you are using.

Unfortunately, OpenAI's gym does not always give reasonable bounds when using env.observation_space, and that seems to be the case for CartPole:

&gt;&gt;&gt; env = gym.make('CartPole-v0')
&gt;&gt;&gt; env.observation_space.high
array([4.8000002e+00, 3.4028235e+38, 4.1887903e-01, 3.4028235e+38],
      dtype=float32)
&gt;&gt;&gt; env.observation_space.low
array([-4.8000002e+00, -3.4028235e+38, -4.1887903e-01, -3.4028235e+38],
      dtype=float32)


Processing this, similarly to your code:

&gt;&gt;&gt; discrete_os_win_size = (env.observation_space.high - env.observation_space.low)/ DISCRETE_OS_SIZE
__main__:1: RuntimeWarning: overflow encountered in subtract
&gt;&gt;&gt; discrete_os_win_size
array([0.48000002,        inf, 0.0418879 ,        inf])

&gt;&gt;&gt; discrete_state = (state - env.observation_space.low)/discrete_os_win_size
&gt;&gt;&gt; discrete_state
array([11.27318768,  0.        , 19.50682776,  0.        ])


That means that all the velocities will get squashed down to $0$ in your approximation. Your agent cannot tell the difference between a nearly static balancing position (generally the goal) and transitioning through it really fast - it will think that both are equally good. It is also not able to tell difference between moving towards balance point, or moving away from it.

I suggest you check for what reasonable bounds are on the space (a quick look suggests +/- 2.0 might be a reasonable starting point) and use that instead.

The approximation approach of discrete grid is also very crude, although it does allow you do use tabular approaches. If you want to stick with a linear system (and avoid trying neural networks and DQN) then the next step up would be some form of tile coding, which uses multiple offset grids to obtain smoother interpolation between states.