In previos section we relied on differently proposing action values and policies. But, what if we could combine these two and use policy in our single update. One approach to do this is to use backpropogation (gradient decent) from ML to update our policy directly, hence the name 'Gradient Bandit'. This method uses preferences (\(H(a_i)\)), similar to action values, and a softmax/boltzman based on prefrences to define a policy. Eventually, the policy becomes, \[\pi(a_i) = \frac{e^{H(a_i)}}{\sum_k e^{H(a_k)}}\] We could start we some intial preferences \(H(a_i)=0\), or assigned randomly, or even optimistic initialization. Agent updates its preferences, policy for an action by realizing how realizing how rewarding has that policy been in the agent's experience. With gradient ascent, this can be formulated as taking a step in direction of how effective/contributing the action has been towards the commulative reward, and written as \(\frac{\delta \mathbb{E}[R]}{\delta H(a_i)}\). And the iterative update could be written as, \[H_{t+1}(a_i) = H_t(a_i) + \alpha \frac{\delta \mathbb{E}[R]}{\delta H(a_i)}\] where, \(\mathbb{E}[R] = \sum_{k} \pi(a_k) r_k\), is expected reward achieved weighted by policy preference of an action. For taking an iterative step, we need to expand the term, \[\frac{\delta \mathbb{E}[R]}{\delta H(a_i)} = \frac{\delta \sum_{k} \pi(a_k) r_k}{\delta H(a_i)} = \sum_{k} r_k \frac{\delta \pi(a_k)}{\delta H(a_i)}\] Further, the term \(\frac{\delta \pi(a_k)}{\delta H(a_i)}\) could be expanded as, \[\frac{\delta \pi(a_k)}{\delta H(a_i)} = \frac{\delta}{\delta H(a_i)} \frac{e^{H(a_k)}}{e^{H(a_i)} + \sum_{p\neq i} e^{H(a_p)}} = \left(\frac{1}{e^{H(a_i)} + \sum_{p\neq i} e^{H(a_p)}}\right) \frac{\delta e^{H(a_k)}}{\delta H(a_i)} + e^{H(a_k)} \frac{-\left(\frac{\delta e^{H(a_i)}}{\delta H(a_i)} + 0 \right)}{\left(e^{H(a_i)} + \sum_{p\neq i} e^{H(a_p)}\right)^2}\] \[ = \frac{1}{\sum_{p} e^{H(a_p)}} \mathbb{1}_{k=i} e^{H(a_k)} - e^{H(a_k)} \frac{e^{H(a_i)}}{(\sum_{p} e^{H(a_p)})^2} = \frac{e^{H(a_k)}}{\sum_p e^{H(a_p)}} \left[\mathbb{1}_{k=i} - \frac{e^{H(a_i)}}{\sum_p e^{H(a_p)}} \right]\] \[\therefore \frac{\delta \pi(a_k)}{\delta H(a_i)} = \pi(a_k) (\mathbb{1}_{k=i} - \pi(a_i)) \text{, putting this back}\] \[\frac{\delta \mathbb{E}[R]}{\delta H(a_i)} = \sum_k r_k \pi(a_k) (\mathbb{1}_{k=i} - \pi(a_i)) = \mathbb{E}_k[(\mathbb{1}_{k=i} - \pi(a_i)) R]\] For a sample, the update equation will become, \[H_{t+1}(a_i) = H_t(a_i) + \alpha r_i (\mathbb{1}_{k=i} - \pi(a_i))\] With this update equation, we can directly update policy and preferences together.
13 Feb 2025.
Next in series: Contextual Bandit.