In this paper, an optimal transmission policy for two-way relay networks is investigated by using a stochastic energy harvesting (EH) model. Considering the channel and finite battery conditions, we propose an optimal relay transmission policy to maximize the long-term achievable sum rate of the network. The design problem is formulated as a Markov decision process (MDP), and the well-known value iteration approach is used to find the optimal policy. Based on the optimal transmission policy, we analyze the expected achievable sum rate and point out a spreading structure for the optimal relay power with respect to the solar panel size. Simulation results demonstrate that our proposed optimal transmission policy outperforms other policies.