一個機器人站在迷宮的起始位置，下圖中的左下角。每一個位置，機器人有四個移動方向，左，右，上，下，當然，對於邊緣情況，它的行動可能被限制。比如，在起始位置，它只能上移或是右移。如果某個移動讓它碰到了障礙，那麼它就被禁止往那個方向移動。在這些設置和條件的情況下，機器人如何能夠通過自學習走出迷宮，也就是說，從迷宮的右上角出來？
這是一個典型的強化學習（reinforcement learning）的例子。它直接將機器人的行動和產生的結果聯繫起來，而不需要機器人學習一個複雜的行動和結果的關係。機器人基於行動的獎賞和懲罰來學習如何走出迷宮。當機器人的移動造成了撞到障礙，那麼它收到懲罰-1分。當它到達一個開闊地帶，那麼它收到獎賞0分（因為是它應該做的事情，不獎不罰）。當它到達出口，那麼它收到一個大大的獎賞100分。這種反饋就是鼓勵機器人做某個動作，或是防止做某個動作的「強化」。
強化學習是從交互中學習，從而成功達到一個目標。學習者和決策者稱作是智能體（比如例中的機器人）。智能體交互的所有外部一切稱作是環境（比如例中的迷宮）。這些交互持續進行，智能體選擇某些行動，環境響應這些行動並且呈現一些新的情境給智能體。同時，環境給出一些獎賞，表現為特殊的數值，而這些數值是智能體希望長期最大化的。一個對環境，包括獎賞如何確定，的完整說明，定義了一個任務，即一個強化學習問題的實例。
更確切的說，智能體和環境在離散的時間序列上交互，t = 0, 1, 2, 3, ... 在每個時間步t，智能體收到環境狀態的某種表示 St ∈ S，其中 S 是所有可能環境狀態的集合。然後智能體選擇一個行動 At ∈ A(St)，其中 A(St) 是在狀態 St 的所有可以選擇的行動的集合。一個時間步之後，作為行動的部分結果，智能體收到一個數值獎賞 Rt+1 ∈ R ⊂ R，並且進入到一個新的環境狀態 St+1。 智能體的目標就是最大化長期的累積獎賞（回報）。對於有限的時間序列，定義回報為時間步t之後的所有獎賞的和，目標就是使之最大。
而對於無限的時間序列，當 T = ∞，上述的回報會區域無窮大，所以需要引入discounting。如下所示的 discounted 回報，γ （ 0 ≤ γ ≤ 1）叫做 discount rate。
在強化學習的框架中，智能體根據環境狀態的信號來做決定。那麼，什麼信息能構成環境狀態的信號呢，這個就涉及到一個屬性，叫做 Markov Property。通常情況下，環境狀態的轉換是和前面路徑上的所有狀態和行動相關的。如下所示。
但是，如果說狀態信號的轉換具有 Markov Property，那麼，它的下一個狀態只與當前狀態和行動相關。這樣就大大簡化了模型。
一個強化學習的任務如果滿足 Makov Property，那麼它就叫做 Markov Decision Process（MDP）。
知道了這個屬性，就可以計算有關環境狀態的各種信息了，比如，state-action 的期望獎賞。
state-transition 概率。
state-action-next-state 的期望獎賞。
幾乎所有強化學習的算法都涉及到估算 value functions（環境狀態 states，或是 state-action 的 functions），而這些 functions 能估算智能體選擇一個行動之後，它所處的下一個狀態是不是比較好（how good）。而這個比較好（how good）定義為將來期望的獎賞（rewards），精確的說，就是期望回報。當然，智能體期望收到的獎賞和它採取的行動密切相關。也就是說，value functions 離不開特定的策略（policies，或 π ）。
一個策略, π, 是一個映射：從環境狀態 s ∈ S 和 行動 a ∈ A(s) 到在環境狀態 s 時採取行動 a 的概率 π(a|s)。有了這個知識，就可以定義一個環境狀態 s 在策略 π 的 value，叫做 state-value function。
同理，定義一個環境狀態 s 在策略 π 下採取行動 a 的 value，in state s under a policy π，叫做 action-value function。
上述的 state-value function 和 value-action function 能夠通過和環境的交互的體驗估算出來。比如，一個智能體遵照策略 π，且對每一個狀態維持一個從這個狀態收到的回報的平均值，當這個狀態被訪問了接近無限次之後，那麼這個平均值就會收斂到 state-value vπ(s)。如果對一個狀態採取的每個行動記錄一個平均值的話，那麼這個平均值就會收斂到 action-value qπ (s, a)。
value function 的一個基本屬性是滿足特定的遞歸關係。這個就是著名的Bellman Equation。
從下面的圖示就很容易理解了。
解決一個強化學習問題，粗略的說，是找到一個策略能夠從長遠獲得許多的回報。對於有限的MDPs，精確的定義最有的策略如下：Value functions 定義了策略的偏序關係。一個策略 π 比另一個策略 π′ 好，如果且只有對於任何的環境狀態，它的期望回報大於 π′。也就是說，對於所有的 s ∈ S，π ≥ π′ iff vπ(s) ≥ vπ′(s)。總是有一個策略好於或是等於其它所有的策略，那麼它就是最有的策略，表示成 π∗。
同理對於 action-value，它的最優q∗。
對於 state–action (s, a)，在環境狀態 s 採取行動 a 的期望回報一定是遵循最優的策略，所以，可以將 q∗ 按 v∗ 表達如下：
下面是Bellman optimality equation，它表達的是，在最優策略下，state value 必須等於在那個環境狀態下採取的最好行動時的期望回報。
對於q∗，Bellman optimality equation 如下：
從下面的圖示就很容易理解了。
有了這些關於強化學習的問題的定義和基礎知識之後，有不同的算法來迭代的解決。
下面介紹一種經常用到的強化學習方法 Q-learning。它學習 action-value function，Q，來近似 q*，最優的 action-value function。
偽碼的實現如下：
應用 Q-learning 到機器人走迷宮的問題。
Q(4, left) = 0 + 0.2 * (0 + 0.9 * Q(1,right) - 0)
Q(4, right) = 0+ 0.2 * (0 + 0.9 * Q(5,up) -0)
這裡，learning rate 是 0.2，且 discount rate 是 0.9。 在狀態1的最好行動是 right，而狀態5的是up。Q(1,right) 和 Q(5,up) 有不同的值，因為從狀態1達到出口比從狀態5需要更多的步數，也就是說，Q(5,up) 比 Q(1,right) 的 value 值更大。也正式這個原因，Q(4,right) 的值比 Q(4, left) 大。那麼，在狀態4的最好的行動是right。重複迭代計算，最後機器人能通過 Q-learning 的方法自學習找到出口，走出迷宮。
參考文獻：
Reinforcement learning explained https://www.oreilly.com/ideas/reinforcement-learning-explained?from=groupmessage&isappinstalled=0
Richard S. Sutton and Andrew G. Barto的《Reinforcement Learning:An Introduction》