Recently, the reciprocal recommendation, especially for online dating applications, has attracted more and more research attention. Different from conventional recommendation problems, the reciprocal recommendation aims to simultaneously best match users' mutual preferences. Intuitively, the mutual preferences might be affected by a few key attributes that users like or dislike. Meanwhile, the interactions between users' attributes and their key attributes are also important for key attributes selection. Motivated by these observations, in this paper we propose a novel reinforced random convolutional network (RRCN) approach for the reciprocal recommendation task. In particular, we technically propose a novel random CNN component that can randomly convolute non-adjacent features to capture their interaction information and learn feature embeddings of key attributes to make the final recommendation. Moreover, we design a reinforcement learning based strategy to integrate with the random CNN component to select salient attributes to form the candidate set of key attributes. We evaluate the proposed RRCN against a number of both baselines and the state-of-the-art approaches on two real-world datasets, and the promising results have demonstrated the superiority of RRCN against the compared approaches in terms of a number of evaluation criteria.