We study the Patrol Security Game (PSG), a robotic patrolling problem formulated as an extensive-form Stackelberg game, in which the attacker strategically selects the timing, location, and duration of an attack. The defender’s goal is to compute an infinite-horizon patrolling policy that minimizes the attacker’s expected payoff. By restricting the defender’s strategy to a time-homogeneous first-order Markov chain, we show that PSG can be reformulated as a combinatorial minimax problem. We prove that the optimal strategy under zero-penalty scenarios corresponds to minimizing either the expected hitting time or return time, depending on the attacker’s visibility model. These optimal policies are closed-form and can be computed efficiently. On the other hand, in high-penalty cases, we observe that the patrolling schedule with high randomness can minimize the attacker’s expected gain. However, in general, the minimax objective becomes non-convex. To address this, we introduce a bi-criteria optimization framework that jointly considers the expected maximum reward (EMR) and entropy rate of the patrolling policy. We propose three graph-based algorithms and a deep reinforcement learning model to efficiently balance these two objectives. Each algorithm demonstrates distinct strengths under different configurations, such as varying penalty scales and cost function settings. The extensive experiments on both synthetic and real-world crime datasets validate the effectiveness of our approaches, demonstrating superior performance and scalability compared to state-of-the-art baselines.