This paper studies the problem of multi-stage robust unit commitment with discrete load shedding. In the day-ahead phase, the on-off status of thermal units is scheduled. During each period of real-time dispatch, the output of thermal units and the action of load shedding are determined, and the discrete choice of load shedding corresponds to the practice of tripping substation outlets. The entire decision-making process is formulated as a multi-stage adaptive robust optimization problem with mixed-integer recourse, whose solution takes three steps. First, we propose and apply partially affine policy, which is optimized ahead of the day and restricts intertemporal dispatch variables as affine functions of previous uncertainty realizations, leaving remaining continuous and binary dispatch variables to be optimized in real time. Second, we demonstrate that the resulting model with partially affine policy can be reformulated as a two-stage robust optimization problem with mixed-integer recourse. Third, we modify the standard nested column-and-constraint generation algorithm to accelerate the inner loops by warm start. The modified algorithm solves the two-stage problem more efficiently. Case studies on the IEEE 118-bus system verify that the proposed partially affine policy outperforms conventional affine policy in terms of optimality and robustness; the modified nested column-and-constraint generation algorithm significantly reduces the total computation time; and the proposed method balances well optimality and efficiency compared with state-of-the-art methods.