Acceleration in a universe with just two objects

Suppose I have a universe with just two objects, say two astronauts, that are placed opposite one another (or alternatively our universe in a very deep and empty region of space with nothing nearby for many many Mpc so that no stars etc. are visible). Then I apply a force on the first astronaut directly parallel to the line between the two astronauts, sending him on a collision course with the second astronaut. The first astronaut feels this force as an acceleration. All well and good so far.

From the second astronaut's perspective the first astronaut started accelerating towards her, so by the laws of motion a force must have been applied on the first astronaut. However the first astronaut can equally reason the exact same way and come to the conclusion that a force must have been applied on the second astronaut to make her accelerate towards him. However we applied no force on the second astronaut and she doesn't feel any acceleration at all, which breaks the expected symmetry of this situation (namely that there is no way to tell whether 1 is accelerating towards 2 or 2 is accelerating towards 1 in a universe with 1 and 2 as the only objects).

I don't understand how to resolve this seeming paradox. Any help is appreciated!